307592: CF1379F1. Chess Strikes Back (easy version)

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Chess Strikes Back (easy version)

题意翻译

给出一个 $2n\times2m$ 的黑白交错棋盘,其中格子 $(1,1)$ 为白色。每次拿走一个白格,问能否在剩下的白格中放入 $n\times m$ 个国王使得它们不互相攻击。 译者 @\_ajthreac\_

题目描述

Note that the difference between easy and hard versions is that in hard version unavailable cells can become available again and in easy version can't. You can make hacks only if all versions are solved. Ildar and Ivan are tired of chess, but they really like the chessboard, so they invented a new game. The field is a chessboard $ 2n \times 2m $ : it has $ 2n $ rows, $ 2m $ columns, and the cell in row $ i $ and column $ j $ is colored white if $ i+j $ is even, and is colored black otherwise. The game proceeds as follows: Ildar marks some of the white cells of the chessboard as unavailable, and asks Ivan to place $ n \times m $ kings on the remaining white cells in such way, so that there are no kings attacking each other. A king can attack another king if they are located in the adjacent cells, sharing an edge or a corner. Ildar would like to explore different combinations of cells. Initially all cells are marked as available, and then he has $ q $ queries. In each query he marks a cell as unavailable. After each query he would like to know whether it is possible to place the kings on the available cells in a desired way. Please help him!

输入输出格式

输入格式


The first line of input contains three integers $ n $ , $ m $ , $ q $ ( $ 1 \leq n, m, q \leq 200\,000 $ ) — the size of the board and the number of queries. $ q $ lines follow, each of them contains a description of a query: two integers $ i $ and $ j $ , denoting a white cell $ (i, j) $ on the board ( $ 1 \leq i \leq 2n $ , $ 1 \leq j \leq 2m $ , $ i + j $ is even) that becomes unavailable. It's guaranteed, that each cell $ (i, j) $ appears in input at most once.

输出格式


Output $ q $ lines, $ i $ -th line should contain answer for a board after $ i $ queries of Ildar. This line should contain "YES" if it is possible to place the kings on the available cells in the desired way, or "NO" otherwise.

输入输出样例

输入样例 #1

1 3 3
1 1
1 5
2 4

输出样例 #1

YES
YES
NO

输入样例 #2

3 2 7
4 2
6 4
1 3
2 2
2 4
4 4
3 1

输出样例 #2

YES
YES
NO
NO
NO
NO
NO

说明

In the first example case after the second query only cells $ (1, 1) $ and $ (1, 5) $ are unavailable. Then Ivan can place three kings on cells $ (2, 2) $ , $ (2, 4) $ and $ (2, 6) $ . After the third query three cells $ (1, 1) $ , $ (1, 5) $ and $ (2, 4) $ are unavailable, so there remain only 3 available cells: $ (2, 2) $ , $ (1, 3) $ and $ (2, 6) $ . Ivan can not put 3 kings on those cells, because kings on cells $ (2, 2) $ and $ (1, 3) $ attack each other, since these cells share a corner.

Input

题意翻译

给出一个 $2n\times2m$ 的黑白交错棋盘,其中格子 $(1,1)$ 为白色。每次拿走一个白格,问能否在剩下的白格中放入 $n\times m$ 个国王使得它们不互相攻击。 译者 @\_ajthreac\_

加入题单

上一题 下一题 算法标签: