Задача №115404. Алиса, Боб и два массива
Алиса и Боб играют в следующую игру на этих массивах: игроки ходят по очереди, на своем ходу игрок должен дописать в конец массива \(c\) число так, что бы \(c\) остался подпоследовательностью \(a\) и подпоследовательностью \(b\). Игрок, который не может сделать ход, проигрывает. Первой ходит Алиса.
Ребята сыграют в игру \(q\) раз. Для \(i\)-й игры они выберут два числа \(x_i\) и \(y_i\) \((0 \leq x_i < N, 0 \leq y_i < M)\), затем удалят из массива \(a\) первые \(x_i\) чисел, из массива \(b\) первые \(y_i\) чисел, после чего сыграют в игру на полученных массивах. После завершения одной операции удаления и до начала следующей они возвращают массивы \(a\) и \(b\) в начальное состояние, то есть числа, удаленные из массива для одной игры, могут быть не удалены в последующих играх. Кроме того, массив \(c\) очищается между играми.
У ребят есть свои причуды, поэтому они всегда выбирают \(x_i\) и \(y_i\) так, чтобы после удалений оставшиеся части массивов \(a\) и \(b\) начинались с одинакового по значению числа .
Алиса очень хочет победить, поэтому просит вас для каждой игры ответить, может ли она выиграть в этой игре, если игроки играют оптимально.
Обратите внимание, что массивы могут быть очень длинными, поэтому они вводятся специальным образом. Каждый массив задается как набор отрезков одинаковых чисел. Массив \(a\) состоит из \(n\) таких отрезков, массив \(b\) состоит из \(m\) таких отрезков. Каждый отрезок задается своей длиной и числом, которое стоит на этом отрезке.
Первая строка содержит шесть целых чисел \(N\), \(n\), \(M\), \(m\), \(k\), \(q\) (\(1 \leq N, M \leq 10^9\), \(1 \leq n, m, k \leq 1600\), \(1 \leq q \leq 10^6\)) — длину первого массива, количество отрезков в первом массиве, длину второго массива, количество отрезков во втором массиве, ограничение на числа и количество игр соответственно.
Следующие \(n\) строк содержат по два целых числа \(l^a_i\) и \(v^a_i\) (\(1 \leq l^a_i \leq N\), \(1 \leq v^a_i \leq k\)) — длину отрезка и число, записанное в этом отрезке. Эти числа задают массив \(a\): первые \(l^a_1\) чисел массива \(a\) равны \(v^a_1\), следующие \(l^a_2\) чисел равны \(v^a_2\), \(\ldots\), последние \(l^a_n\) чисел равны \(v^a_n\).
Следующие \(m\) строк содержат по два целых числа \(l^b_i\) и \(v^b_i\) (\(1 \leq l^b_i \leq N\), \(1 \leq v^b_i \leq k\)) — длину отрезка и число, записанное в этом отрезке. Эти числа задают массив \(b\). Формат аналогичен массиву \(a\).
Гарантируется, что \(\sum l^a_i = N\), \(\sum l^b_i = M\), \(v^a_i \neq v^a_{i+1}\) и \(v^b_i \neq v^b_{i+1}\).
Следующие \(q\) строк содержат пары целых чисел \(x_i\) и \(y_i\) (\(0 \le x_i < N\), \(0 \le y_i < M\)) — описания игр.
Для каждой игры \(i\) гарантируется, что если удалить из \(a\) первые \(x_i\) символов, а из \(b\) первые \(y_i\) символов, то массивы будут начинаться с одинакового по значению числа.
Для каждой из \(q\) игр в отдельной строке выведите « Yes », если при оптимальной стратегии игроков выигрывает Алиса, и « No », если Боб.
В первом примере массивы выглядят так: \(a = (1, 1, 1, 1, 1)\) и \(b = (1, 1, 1, 1, 1)\).
- В первом запросе \(x = 0, y = 0\), а значит игра будет проходить на массивах \(a = (1, 1, 1, 1, 1)\) и \(b = (1, 1, 1, 1, 1)\). В данном случае игроки могут записывать в конец массива \(c\), только число \(1\), поэтому через 5 ходов игра закончится и Боб проиграет, так как не сможет сделать ход.
- Во втором запросе \(x = 0, y = 1\), а значит игра будет проходить на массивах \(a = (1, 1, 1, 1, 1)\) и \(b = (1, 1, 1, 1)\). В данном случае игра закончится за 4 хода и Алиса проиграет.
- В последнем запросе \(x = 2, y = 2\), а значит игра будет проходить на массивах \(a = (1, 1, 1)\) и \(b = (1, 1, 1)\). В данном случае Боб проиграет.
Во втором примере \(a = (1, 1, 2, 2, 2, 1, 1)\), \(b = (2, 2, 1, 1, 1, 2, 2)\).
- В первом запросе \(x=0\) и \(y = 2\), поэтому игра будет проходить на массивах \(a = (1, 1, 2, 2, 2, 1, 1)\) и \(b = (1, 1, 1, 2, 2)\). Если Алиса допишет в конец массива число \(2\), то Боб тоже может дописать число \(2\), после чего не останется ходов и Алиса проиграет. Поэтому вначале Алиса должна дописать в \(c\) число \(1\). После этого, по аналогичным причинам, если Боб допишет в массив \(c\) число \(2\), то проиграет. Поэтому он вынужден дописывать число \(1\), после чего \(c = (1, 1)\). Далее Алиса опять дописывает в массив \(c\) число \(1\) и у Боба не остаётся ходов, поэтому Алиса побеждает.
- Во втором запросе \(x = 0\) и \(y = 3\), поэтому игра будет проходить на массивах \(a = (1, 1, 2, 2, 2, 1, 1)\) и \(b = (1, 1, 2, 2)\). Аналогично рассуждениям к предыдущему примеру, Алиса не может дописать в конец массива \(c\) число \(2\), потому что иначе проиграет. Но если Алиса допишет в конец массива \(c\) число \(1\), то Боб тоже допишет число \(1\), после чего Алиса проигрывает по аналогичным причинам. Поэтому в этом случае побеждает Боб.
Тесты к этой задаче состоят из одиннадцати групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, что прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Ограничения | ||||||
| Группа | Баллы | \(N\), \(M\) | \(n\), \(m\) | \(q\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 13 | \(N, M \le 300\) | – | \(q \le 10^5\) | 0 | |
| 2 | 12 | \(N, M \le 5000\) | – | \(q \le 10^5\) | 0, 1 | |
| 3 | 11 | – | – | \(q \le 10^5\) | – | \(l^a_i \le 1000\) и все \(v^a_i\) различны \(l^b_i \le 1000\) и все \(v^b_i\) различны |
| 4 | 8 | – | – | \(q \le 10^5\) | 3 | \(l^a_i \le 1000\) и все \(v^a_i\) различны |
| 5 | 10 | – | – | \(q \le 10^5\) | – | \(l^a_1 \ge N - 500\) и \(v^a_1 = 1\) \(l^b_1 \ge M - 500\) и \(v^b_1 = 1\) |
| 6 | 7 | \(N, M \le 10^5\) | \(n, m \le 100\) | \(q \le 10^5\) | – | \(k \le 5\) |
| 7 | 6 | \(N, M \le 10^5\) | \(n, m \le 100\) | \(q \le 10^5\) | 0, 6 | \(k \le 50\) |
| 8 | 7 | – | \(n, m \le 100\) | \(q \le 10^5\) | 0, 6, 7 | \(k \le 50\) |
| 9 | 9 | – | \(n, m \le 800\) | \(q \le 10^5\) | 0, 6 – 8 | |
| 10 | 10 | – | – | \(q \le 10^5\) | 0 – 9 | Offline-проверка. |
| 11 | 7 | – | – | – | 0 – 10 | Offline-проверка. |
5 1 5 1 1 9 5 1 5 1 0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2
Yes No Yes No No Yes Yes Yes Yes
7 3 7 3 2 12 2 1 3 2 2 1 2 2 3 1 2 2 0 2 0 3 0 4 1 2 1 3 1 4 2 5 2 6 3 5 3 6 4 5 4 6
Yes No Yes Yes No Yes No Yes No Yes Yes Yes