2. JOI 2023 - Cell Automaton
Ta có một lưới hai chiều đủ lớn gồm các ô vuông, trải theo cả chiều ngang và chiều dọc. Chọn một ô làm gốc tọa độ. Ô \((x,y)\) là ô đến được khi đi từ gốc sang phải \(x\) ô và lên trên \(y\) ô. Đi sang trái \(a\) ô tương ứng với đi sang phải \(-a\) ô; đi xuống dưới \(a\) ô tương ứng với đi lên trên \(-a\) ô.
Tại thời điểm \(0\), các ô \((X_1,Y_1),(X_2,Y_2),\ldots,(X_N,Y_N)\) có màu đen, và tất cả các ô còn lại có màu trắng.
Với \(t=0,1,2,\ldots\), màu của các ô tại thời điểm \(t+1\) được xác định từ màu tại thời điểm \(t\) như sau:
- Một ô màu đen tại thời điểm \(t\) chuyển thành màu xám tại thời điểm \(t+1\).
- Một ô màu xám tại thời điểm \(t\) chuyển thành màu trắng tại thời điểm \(t+1\).
- Một ô màu trắng tại thời điểm \(t\) chuyển thành màu đen tại thời điểm \(t+1\) nếu ít nhất một trong bốn ô kề cạnh với nó có màu đen tại thời điểm \(t\). Nếu không, ô đó vẫn có màu trắng.
Có \(Q\) truy vấn. Với truy vấn thứ \(j\) (\(1 \le j \le Q\)), hãy tìm số ô màu đen tại thời điểm \(T_j\).
Hãy viết chương trình trả lời các truy vấn khi biết màu của các ô tại thời điểm \(0\) và thông tin truy vấn.
Dữ liệu vào
Đọc từ đầu vào chuẩn theo định dạng:
N Q
X_1 Y_1
X_2 Y_2
...
X_N Y_N
T_1
T_2
...
T_Q
Dữ liệu ra
Ghi \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(j\) chứa số ô màu đen tại thời điểm \(T_j\).
Ràng buộc
- \(1 \le N \le 100000\).
- \(1 \le Q \le 500000\).
- \(|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\)).
- Tất cả các giá trị đầu vào đều là số nguyên.
Phân nhóm
- \(4\) điểm: \(\lvert X_i\rvert \le 50\), \(\lvert Y_i\rvert \le 50\) với mọi \(1 \le i \le N\); \(T_j \le 50\) với mọi \(1 \le j \le Q\).
- \(12\) điểm: \(\lvert X_i\rvert \le 1000\), \(\lvert Y_i\rvert \le 1000\) với mọi \(1 \le i \le N\); \(T_j \le 1000\) với mọi \(1 \le j \le Q\).
- \(8\) điểm: \(X_i=Y_i\) với mọi \(1 \le i \le N\); \(Q=1\).
- \(8\) điểm: \(X_i=Y_i\) với mọi \(1 \le i \le N\).
- \(17\) điểm: \(N \le 2000\); \(Q=1\).
- \(25\) điểm: \(N \le 2000\).
- \(26\) điểm: Không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Input
2 3
0 2
1 0
0
1
2Output
2
8
12Giải thích
Hình dưới đây thể hiện màu các ô tại thời điểm \(0\). Có \(2\) ô màu đen, nên đáp án của truy vấn thứ nhất là \(2\).
Hình dưới đây thể hiện màu các ô tại thời điểm \(1\). Có \(8\) ô màu đen, nên đáp án của truy vấn thứ hai là \(8\).
Hình dưới đây thể hiện màu các ô tại thời điểm \(2\). Có \(12\) ô màu đen, nên đáp án của truy vấn thứ ba là \(12\).
Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,2,6,7\).
Ví dụ 2
Input
3 5
0 0
2 2
5 5
0
1
2
3
4Output
3
12
21
24
26Giải thích
Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,2,4,6,7\).
Ví dụ 3
Input
4 10
-3 -3
3 3
-4 4
4 -4
0
1
2
3
4
5
6
7
8
9Output
4
16
32
48
56
56
55
56
60
64Giải thích
Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,2,6,7\).
Nguồn
JOI Open Contest 2023 - Cell Automaton. Tác giả: Akihito Yoneyama. Đơn vị công bố: JCIOI (Ủy ban Nhật Bản về Olympic Tin học Quốc tế). Giấy phép: CC BY-SA 4.0.
