{"problem":{"name":"[JOI Open 2023] 细胞自动机 / Cell Automaton","description":{"content":"我们有一个充分大的二维网格，网格由从上到下和从左到右的正方形单元格密铺而成。 有一个单元格是坐标原点。令 $(x,y)$ 表示表示从原点向右移动 $x$ 个单元格，再向上移动 $y$ 个单元格所到达的单元格。这里，向左移动 $a$ 个单元格意味着向右移动 $-a$ 个单元格。类似地，向下移动 $a$ 个单元格意味着向上移动 $-a$ 个单元格。 在时刻 $0$，单元格 $(X_1,Y_1),(","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":6000,"memory_limit":2097152},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9513"},"statements":[{"statement_type":"Markdown","content":"我们有一个充分大的二维网格，网格由从上到下和从左到右的正方形单元格密铺而成。\n\n有一个单元格是坐标原点。令 $(x,y)$ 表示表示从原点向右移动 $x$ 个单元格，再向上移动 $y$ 个单元格所到达的单元格。这里，向左移动 $a$ 个单元格意味着向右移动 $-a$ 个单元格。类似地，向下移动 $a$ 个单元格意味着向上移动 $-a$ 个单元格。\n\n在时刻 $0$，单元格 $(X_1,Y_1),(X_2,Y_2),\\ldots,(X_N,Y_N)$ 是黑色的，其余单元格是白色的。\n\n对于 $t=0,1,2,\\ldots$，根据单元格在 $t$ 时刻的颜色，单元格在 $t+1$ 时刻的颜色按如下方法确定：\n\n- 如果在时刻 $t$ 时单元格是黑色，那么在时刻 $t+1$ 这个单元格变为灰色。\n- 如果在时刻 $t$ 时单元格是灰色，那么在时刻 $t+1$ 这个单元格变为白色。\n- 如果在时刻 $t$ 时单元格是白色，并且与其相邻的四个单元格（即，与其共边的四个单元格）中至少有一个在时刻 $t$ 是黑色的，那么在时刻 $t+1$ 这个单元格变为黑色。否则，它将在时刻 $t+1$ 保持白色。\n\n你有 $Q$ 次查询。对于第 $j$ 个查询，你应该回答在时刻 $T_j$ 时有多少黑色单元格。\n\n给定在时刻 $0$ 时的单元格颜色信息和查询，写一个程序回答询问。\n\n## Input\n\n第一行两个整数 $N,Q$。\n\n接下来 $N$ 行，每行两个整数 $X_i,Y_i$。\n\n接下来 $Q$ 行，每行一个整数 $T_j$。\n\n## Output\n\n输出 $Q$ 行，每行一个整数，表示在时刻 $T_j$ 时有多少黑色单元格。\n\n[samples]\n\n## Background\n\n**译自 [JOI Open 2023](https://contests.ioi-jp.org/open-2023/index.html) T2 「[セルオートマトン](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2023/cell/2023-open-cell-statement.pdf) / [Cell Automaton](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2023/cell/2023-open-cell-statement-en.pdf)」**\n\n## Note\n\n**【样例解释 #1】**\n\n下图展示了在时刻 $0$ 时的单元格情况。因为有 $2$ 个黑色单元格，所以第一个询问的回答是 $2$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/6mmzh2tq.png)\n\n下图展示了在时刻 $1$ 时的单元格情况。因为有 $8$ 个黑色单元格，所以第二个询问的回答是 $8$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/s5gw87z0.png)\n\n下图展示了在时刻 $2$ 时的单元格情况。因为有 $12$ 个黑色单元格，所以第三个询问的回答是 $12$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/2uavkaeg.png)\n\n这组样例满足子任务 $1,2,6,7$ 的限制。\n\n**【样例解释 #2】**\n\n这组样例满足子任务 $1,2,4,6,7$ 的限制。\n\n**【样例解释 #3】**\n\n这组样例满足子任务 $1,2,6,7$ 的限制。\n\n**【数据范围】**\n\n对于所有数据，满足：\n\n- $1\\le N\\le 10^5$\n- $1\\le Q\\le 5\\times 10^5$\n- $|X_i|,|Y_i|\\le 10^9$\n- $(X_i,Y_i)\\neq (X_j,Y_j)\\ (1\\le i < j\\le N)$\n- $0\\le T_j\\le 10^9$\n- $T_j<T_{j+1}$\n\n详细子任务附加限制及分值如下表所示。\n\n| 子任务 |               附加限制                | 分值 |\n| :----: | :-----------------------------------: | :--: |\n|  $1$   |     $\\lvert X_i\\rvert ,\\lvert Y_i\\rvert \\le 50,T_j\\le 50$     | $4$  |\n|  $2$   | $\\lvert X_i\\rvert ,\\lvert Y_i\\rvert \\le 1\\ 000,T_j\\le 1\\ 000$ | $12$ |\n|  $3$   |             $X_i=Y_i,Q=1$             | $8$  |\n|  $4$   |               $X_i=Y_i$               | $8$  |\n|  $5$   |           $N\\le 2\\ 000,Q=1$           | $17$ |\n|  $6$   |             $N\\le 2\\ 000$             | $25$ |\n|  $7$   |              无附加限制               | $26$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9513","tags":["2023","O2优化","JOI（日本）"],"sample_group":[["2 3\n0 2\n1 0\n0\n1\n2\n","2\n8\n12\n"],["3 5\n0 0\n2 2\n5 5\n0\n1\n2\n3\n4\n","3\n12\n21\n24\n26\n"],["4 10\n-3 -3\n3 3\n-4 4\n4 -4\n0\n1\n2\n3\n4\n5\n6\n7\n8\n9\n","4\n16\n32\n48\n56\n56\n55\n56\n60\n64\n"]],"created_at":"2026-03-03 11:09:25"}}