← 返回题目列表

Codeforces · 1379/F1

F1. 国际象棋反击(简单版)

中文机器翻译题面 查看原题

请注意,简单版本和困难版本之间的区别在于,在困难版本中不可用的单元格可以再次变得可用,而在简单版本中则不能。只有解决了所有版本才可以进行黑客攻击。

伊尔达和伊万厌倦了国际象棋,但他们真的很喜欢棋盘,所以他们发明了一种新游戏。该字段是一个棋盘 $$$2n \times 2m$$$:它有 $$$2n$$$ 行,$$$2m$$$ 列,如果 $$$i+j$$$ 是偶数,则行 $$$i$$$ 和列 $$$j$$$ 中的单元格颜色为白色,否则颜色为黑色。

游戏进行如下:Ildar 将棋盘上的一些白方格标记为不可用,并要求 Ivan 将 $$$n \times m$$$ 个王以这种方式放置在剩余的白方格上,这样就不会有王互相攻击。如果国王位于相邻的单元格中,共享边缘或角落,则国王可以攻击另一个国王。

Ildar 希望探索不同的细胞组合。最初,所有单元格都标记为可用,然后他有 $$$q$$$ 查询。在每个查询中,他将一个单元格标记为不可用。每次查询后,他想知道是否可以以所需的方式将国王放置在可用的单元格上。请帮助他!

输入

输入的第一行包含三个整数 $$$n$$$, $$$m$$$, $$$q$$$ ($$$1 \leq n, m, q \leq 200\,000$$$) - 棋盘的大小和查询的数量。

$$$q$$$ 行如下,每行包含一个查询的描述:两个整数 $$$i$$$ 和 $$$j$$$,表示板上的一个白色单元格 $$$(i, j)$$$ ($$$1 \leq i \leq 2n$$$, $$$1 \leq j \leq 2m$$$, $$$i + j$$$ 是甚至)变得不可用。保证每个单元格 $$$(i, j)$$$ 在输入中最多出现一次。

输出

输出 $$$q$$$ 行,第 $$$i$$$ 行应包含 Ildar $$$i$$$ 查询后的棋盘答案。如果可以以所需的方式将国王放置在可用单元格上,则该行应包含“是”,否则应包含“否”。

示例

输入 #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

注意

在第二个查询后的第一个示例中,仅单元格 $$$(1, 1)$$$ 和 $$$(1, 5)$$$ 不可用。然后 Ivan 可以将三个国王放在单元格 $$$(2, 2)$$$、$$$(2, 4)$$$ 和 $$$(2, 6)$$$ 上。

第三次查询后,三个单元格 $$$(1, 1)$$$、$$$(1, 5)$$$ 和 $$$(2, 4)$$$ 不可用,因此只剩下 3 个可用单元格:$$$(2, 2)$$$、$$$(1, 3)$$$ 和 $$$(2, 6)$$$。 Ivan 不能在这些单元格上放置 3 个国王,因为单元格 $$$(2, 2)$$$ 和 $$$(1, 3)$$$ 上的国王会互相攻击,因为这些单元格共享一个角。