Задача №115017. Шахматные баталии
Участникам, использующим язык Python3 , рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3 .
Ильдар и Ваня устали постоянно играть в шахматы, поэтому они придумали новую шахматную игру.
Игра происходит на шахматном поле размером \(2n \times 2m\). Это поле имеет \(2n\) строк и \(2m\) столбцов. Для удобства будем обозначать как \((i, j)\) клетку поля, которая находится в \(i\)-й строке и \(j\)-м столбце. Клетки этого поля покрашены в черный и белый цвета шахматной раскраской. Более точно, клетка \((i, j)\) имеет белый цвет, если \(i+j\) чётно, и чёрный цвет в противном случае.
Игра устроена следующим образом. Ильдар вырезает некоторые белые клетки поля. После этого он предлагает Ване попробовать решить следующую задачу: может ли он на не вырезанных белых клетках поля расставить \(nm\) шахматных королей так, что никакие два выставленных короля не бьют друг друга, то есть не стоят на клетках поля, соседних по стороне или углу.
Конечно, Ильдар планирует сделать игру интересной и выставить несколько непростых для Вани комбинаций вырезанных клеток. Для этого он попросил у вас помощи. Чтобы перед игрой понять, как лучше всего действовать, он хочет потренироваться. Для этого, он берёт пустое поле и хочет \(q\) раз либо вырезать какую-то белую клетку, либо вернуть на поле какую-то ранее вырезанную клетку. После каждого изменения он бы хотел знать, каким будет ответ на задачу для Вани.
Помогите Ильдару сделать игру интересной! Напишите программу, которая будет отвечать на его запросы.
В первой строке находится три целых числа \(n\), \(m\), \(q\) (\(1 \leq n, m, q \leq 200\,000\)) — количество пар строк шахматной доски, количество пар столбцов шахматной доски и количество запросов.
Следующие \(q\) строк описывают запросы Ильдара. Каждая из этих строк содержит два целых числа \(i\), \(j\) (\(1 \leq i \leq 2n\), \(1 \leq j \leq 2m\), \(i + j\) четно). Если клетка \((i, j)\) не вырезана, то Ильдар её вырезает, иначе он возвращает её обратно на поле.
Выведите \(q\) строк. В \(i\)-й из этих строк выведите ответ на задачу для доски, полученной после \(i\) первых запросов Ильдара.
Выведите « YES » (без кавычек), если Ваня может так расставить шахматных королей на не вырезанные белые клетки поля, что никакие два короля не будут бить друг друга. Иначе выведете « NO » (без кавычек).
В первом примере, после второго запроса будут вырезаны клетки \((1, 1)\) и \((1, 5)\). Тогда Ваня может поставить три короля на клетки \((2, 2)\), \((2, 4)\) и \((2, 6)\).
После третьего запроса будут вырезаны клетки \((1, 1)\), \((1, 5)\) и \((2, 4)\). Тогда остаётся всего три пустые клетки \((2, 2)\), \((1, 3)\) и \((2, 6)\). Ваня не может поставить трех королей на эти клетки, потому что короли в клетках \((2, 2)\) и \((1, 3)\) бьют друг друга, так как эти клетки соседние по углу.
Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Дополнительные ограничения | ||||||
| Группа | Баллы | \(n\) | \(m\) | \(q\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 10 | \(n = 1\) | \(m \leq 100\) | \(q \leq 100\) | – | |
| 2 | 10 | \(n \leq 3\) | \(m \leq 3\) | \(q \leq 20\) | 0 | |
| 3 | 15 | \(n \leq 100\) | \(m \leq 100\) | \(q \leq 500\) | 0 – 2 | |
| 4 | 15 | \(n \leq 3000\) | \(m \leq 3000\) | \(q \leq 3000\) | 0 – 3 | |
| 5 | 20 | – | – | – | – | Клетки не возвращаются |
| 6 | 30 | – | – | – | 0 – 5 | |
1 3 3 1 1 1 5 2 4
YES YES NO
3 2 10 4 2 6 4 1 3 4 2 6 4 2 2 2 4 1 3 4 4 3 1
YES YES NO NO YES YES NO YES YES NO