Codeforces Round 814 (Div. 1) |
---|
Закончено |
Назовем массив $$$a$$$ чистым, если в нем все элементы попарно различны. Например, массив $$$[1, 7, 9]$$$ — чистый, а $$$[1, 3, 3, 7]$$$ — нет, ведь $$$3$$$ встречается в нем дважды.
Чистый массив $$$b$$$ похож на чистый массив $$$c$$$, если их длина $$$n$$$ одинакова, и для всех пар индексов $$$l$$$, $$$r$$$ таких, что $$$1 \le l \le r \le n$$$, выполняется $$$$$$\operatorname{argmax}([b_l, b_{l + 1}, \ldots, b_r]) = \operatorname{argmax}([c_l, c_{l + 1}, \ldots, c_r]),$$$$$$ где $$$\operatorname{argmax}(x)$$$ — индекс наибольшего элемента в $$$x$$$ (уникального для чистых массивов). Например, $$$\operatorname{argmax}([3, 4, 2]) = 2$$$, $$$\operatorname{argmax}([1337, 179, 57]) = 1$$$.
Недавно Тоня узнал, что Бурёнке очень нравится перестановка $$$p$$$ длины $$$n$$$. Тоня решил обрадовать Бурёнку и подарить ей массив $$$a$$$, похожий на $$$p$$$. Он уже зафиксировал некоторые элементы $$$a$$$, но ровно $$$k$$$ элементов отсутствуют (в этих позициях сейчас $$$a_i = 0$$$). Гарантируется, что $$$k \ge 2$$$. Кроме того, у Тони есть множество $$$S$$$ из $$$k - 1$$$ числа.
Тоня понял, что для того, чтобы заполнить пропуски в массиве $$$a$$$ ему не хватает одного числа, поэтому он решил купить его. У него есть $$$q$$$ вариантов покупки. Тоня считает, что число $$$d$$$ подходит ему, если можно заполнить пропуски в $$$a$$$ числами из $$$S$$$ и числом $$$d$$$ так, чтобы $$$a$$$ стал чистым массивом, похожим на $$$p$$$. Для каждого варианта покупки числа $$$d$$$ выведите, подходит ли Тоне это число или нет.
В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных содержится два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$) — длина перестановки и количество вариантов покупки.
Во второй строке каждого набора входных данных содержатся $$$n$$$ различных целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — перестановка, которая нравится Бурёнке.
В третьей строке каждого набора входных данных содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^6$$$) — элементы массива, где $$$0$$$ означает место, которое нужно заполнить. Гарантируется, что существуют два индекса $$$i, j$$$ $$$(1 \le i, j \le n, i \ne j)$$$ такие, что $$$a_i = 0, a_j = 0$$$ из чего следует, что $$$k \geq 2$$$.
В четвертой строке каждого набора входных данных содержится $$$k - 1$$$ число $$$s_1, s_2, \ldots, s_{k-1}$$$ ($$$1 \le s_i \le 10^6$$$) — числа, которые есть у Тони во множестве $$$S$$$.
Каждая из следующих $$$q$$$ строк содержит одно целое число $$$d$$$ ($$$1 \le d \le 10^6$$$) – число, которое планирует купить Тоня.
Гарантируется, что для каждого данного $$$d$$$ существует способ заполнить пропуски в $$$a$$$ числами из $$$S$$$ и числом $$$d$$$ так, чтобы получить чистый массив.
Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ по всем тестам не превосходят $$$3 \cdot 10^5$$$.
Для каждого набора входных данных выведите $$$q$$$ строк. Для каждого значения $$$d$$$ выведите «YES», если существует способ заполнить массив $$$a$$$, сделав его похожим на $$$p$$$, и «NO» в противном случае.
44 31 4 3 25 0 7 069145 31 2 5 4 30 5 10 0 03 918115 21 4 3 2 50 0 0 0 07 9 1 561004 24 1 3 20 5 3 0246
YES NO NO YES YES NO YES YES NO NO
В первом наборе входных данных для $$$d = 9$$$ можно получить $$$a = [5, 9, 7, 6]$$$, можно доказать, что такое $$$a$$$ похоже на $$$p$$$, для $$$d=1$$$ и $$$d=4$$$ можно доказать, что ответа не существует.
Во втором наборе входных данных для $$$d = 1$$$ можно получить $$$a = [1, 5, 10, 9, 3]$$$, для $$$d = 8$$$ можно получить $$$a = [3, 5, 10, 9, 8]$$$, можно доказать, что для $$$d = 11$$$ ответа не существует.
Название |
---|