Codeforces Round 624 (Div. 3) |
---|
Закончено |
Вам задан массив $$$a$$$ длины $$$n$$$.
Кроме того, вам задано множество различных позиций $$$p_1, p_2, \dots, p_m$$$, где $$$1 \le p_i < n$$$. Позиция $$$p_i$$$ означает, что вы можете поменять местами элементы $$$a[p_i]$$$ и $$$a[p_i + 1]$$$. Вы можете применить эту операцию любое количество раз для каждой из заданных позиций.
Ваша задача — определить, возможно ли отсортировать заданный массив в неубывающем порядке ($$$a_1 \le a_2 \le \dots \le a_n$$$), используя только разрешенные обмены местами.
Например, если $$$a = [3, 2, 1]$$$ и $$$p = [1, 2]$$$, то сначала мы можем поменять местами элементы $$$a[2]$$$ и $$$a[3]$$$ (т.к. позиция $$$2$$$ содержится в заданном множестве $$$p$$$). Получим массив $$$a = [3, 1, 2]$$$. Затем поменяем местами $$$a[1]$$$ и $$$a[2]$$$ (позиция $$$1$$$ также содержится в $$$p$$$). Получим массив $$$a = [1, 3, 2]$$$. Наконец, снова поменяем местами $$$a[2]$$$ и $$$a[3]$$$ и получим массив $$$a = [1, 2, 3]$$$, отсортированный в порядке неубывания.
Вы можете заметить, что если $$$a = [4, 1, 2, 3]$$$ и $$$p = [3, 2]$$$, то отсортировать массив невозможно.
Вам требуется ответить на $$$t$$$ независимых наборов тестовых данных.
Первая строка теста содержит одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.
Затем следуют $$$t$$$ наборов входных данных. Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le m < n \le 100$$$) — количество элементов в $$$a$$$ и количество элементов в $$$p$$$. Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$). Третья строка каждого набора содержит $$$m$$$ целых чисел $$$p_1, p_2, \dots, p_m$$$ ($$$1 \le p_i < n$$$, все $$$p_i$$$ различны) — множество позиций, описанное в условии задачи.
Для каждого набора тестовых данных выведите ответ на него — «YES» (без кавычек), если возможно отсортировать заданный массив в неубывающем порядке ($$$a_1 \le a_2 \le \dots \le a_n$$$), используя только разрешенные обмены местами. Иначе выведите «NO».
6 3 2 3 2 1 1 2 4 2 4 1 2 3 3 2 5 1 1 2 3 4 5 1 4 2 2 1 4 3 1 3 4 2 4 3 2 1 1 3 5 2 2 1 2 3 3 1 4
YES NO YES YES NO YES
Название |
---|