2023-open-t2_Cell_Automaton — JOI JOI_open
Task type: batch | Time limit: 6 s | Memory limit: 2048 MB | Difficulty: 24
Algorithms: line sweep, geometry, recurrence, coordinate compression

# Cell Automaton

![](_page_0_Picture_0.jpeg)

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)  
JOI Open Contest  
August 5, 2023

We have a sufficiently large 2-dimensional grid of cells. The grid is paved with square cells from the top to the bottom and from the left to the right.

There is a cell, which is the origin of the coordinates. Let $(x, y)$ denote the cell one arrives at when one moves from the origin to the right direction for the distance of $x$ cells and to the upward direction for the distance of $y$ cells. Here, the left direction for the distance of $a$ cells means the right direction for the distance of $-a$ cells. Similarly, the downward direction for the distance of $a$ cells means the upward direction of $-a$ cells.

At time 0, the cells $(X_1, Y_1), (X_2, Y_2), ..., (X_N, Y_N)$ are black, and all of the other cells are white.

For $t = 0, 1, 2, ...$, the colors of the cells at time $t + 1$ are determined by the colors of the cells at time $t$ in the following way:

*   If a cell is black at time $t$, then the cell becomes gray at time $t + 1$.
*   If a cell is gray at time $t$, then the cell becomes white at time $t + 1$.
*   A cell which is white at time $t$ becomes black at time $t + 1$ if at least one of the 4 adjacent cells (i.e., the 4 cells which share the edges) is black at time $t$. Otherwise, it remains white at time $t + 1$.

You have $Q$ queries. For the $j$-th ($1 \le j \le Q$) query, you should answer the number of black cells at time $T_j$. Write a program which, given the information of the colors of the cells at time 0 and queries, answers the queries.

## Input

Read the following data from the standard input:

```
N Q
X_1 Y_1
X_2 Y_2
...
X_N Y_N
T_1
T_2
...
T_Q
```

![](_page_1_Picture_0.jpeg)

## Output

Write $Q$ lines to the standard output. The $j$-th line should contain the number of black cells at time $T_j$.

## Constraints

*   $1 \le N \le 100\,000$.
*   $1 \le Q \le 500\,000$.
*   $|X_i| \le 10^9$ ($1 \le i \le N$).
*   $|Y_i| \le 10^9$ ($1 \le i \le N$).
*   $(X_i, Y_i) \ne (X_j, Y_j)$ ($1 \le i < j \le N$).
*   $0 \le T_j \le 10^9$ ($1 \le j \le Q$).
*   $T_j < T_{j+1}$ ($1 \le j \le Q - 1$).
*   Given values are all integers.

## Subtasks

1.  (4 points) $|X_i| \le 50$ ($1 \le i \le N$), $|Y_i| \le 50$ ($1 \le i \le N$), $T_j \le 50$ ($1 \le j \le Q$).
2.  (12 points) $|X_i| \le 1\,000$ ($1 \le i \le N$), $|Y_i| \le 1\,000$ ($1 \le i \le N$), $T_j \le 1\,000$ ($1 \le j \le Q$).
3.  (8 points) $X_i = Y_i$ ($1 \le i \le N$), $Q = 1$.
4.  (8 points) $X_i = Y_i$ ($1 \le i \le N$).
5.  (17 points) $N \le 2\,000$, $Q = 1$.
6.  (25 points) $N \le 2\,000$.
7.  (26 points) No additional constraints.

![](_page_2_Picture_0.jpeg)

## Sample Input and Output

**Sample Input 1**

```
2 3
0 2
1 0
0
1
2
```

**Sample Output 1**

```
2
8
12
```

The following figure shows the colors of the cells at time 0. Since there are 2 black cells, the answer to the first query is 2.

![](_page_2_Figure_6.jpeg)

![](_page_3_Picture_0.jpeg)

The following figure shows the colors of the cells at time 1. Since there are 8 black cells, the answer to the second query is 8.

![](_page_3_Figure_4.jpeg)

![](_page_4_Picture_0.jpeg)

The following figure shows the colors of the cells at time 2. Since there are 12 black cells, the answer to the third query is 12.

![](_page_4_Figure_4.jpeg)

This sample input satisfies the constraints of Subtasks 1, 2, 6, 7.

![](_page_5_Picture_0.jpeg)

**Sample Input 2**

```
3 5
0 0
2 2
5 5
0
1
2
3
4
```

**Sample Output 2**

```
3
12
21
24
26
```

This sample input satisfies the constraints of Subtasks 1, 2, 4, 6, 7.

**Sample Input 3**

```
4 10
-3 -3
3 3
-4 4
4 -4
0
1
2
3
4
5
6
7
8
9
```

**Sample Output 3**

```
4
16
32
48
56
56
55
56
60
64
```

This sample input satisfies the constraints of Subtasks 1, 2, 6, 7.

Starter code: