1311B.md (2150B)
1 Source: https://codeforces.com/problemset/problem/1311/B 2 3 B. WeirdSort 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an array $a$ of length $n$. 22 23 You are also given a set of distinct positions $p_1, p_2, \dots, p_m$, where $1 \le p_i \lt n$. The position $p_i$ means that you can swap elements $a[p_i]$ and $a[p_i + 1]$. You can apply this operation any number of times for each of the given positions. 24 25 Your task is to determine if it is possible to sort the initial array in non-decreasing order ($a_1 \le a_2 \le \dots \le a_n$) using only allowed swaps. 26 27 For example, if $a = [3, 2, 1]$ and $p = [1, 2]$, then we can first swap elements $a[2]$ and $a[3]$ (because position $2$ is contained in the given set $p$). We get the array $a = [3, 1, 2]$. Then we swap $a[1]$ and $a[2]$ (position $1$ is also contained in $p$). We get the array $a = [1, 3, 2]$. Finally, we swap $a[2]$ and $a[3]$ again and get the array $a = [1, 2, 3]$, sorted in non-decreasing order. 28 29 You can see that if $a = [4, 1, 2, 3]$ and $p = [3, 2]$ then you cannot sort the array. 30 31 You have to answer $t$ independent test cases. 32 33 Input 34 35 The first line of the input contains one integer $t$ ($1 \le t \le 100$) — the number of test cases. 36 37 Then $t$ test cases follow. The first line of each test case contains two integers $n$ and $m$ ($1 \le m \lt n \le 100$) — the number of elements in $a$ and the number of elements in $p$. The second line of the test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 100$). The third line of the test case contains $m$ integers $p_1, p_2, \dots, p_m$ ($1 \le p_i \lt n$, all $p_i$ are distinct) — the set of positions described in the problem statement. 38 39 Output 40 41 For each test case, print the answer — "YES" (without quotes) if you can sort the initial array in non-decreasing order ($a_1 \le a_2 \le \dots \le a_n$) using only allowed swaps. Otherwise, print "NO". 42 43 Example 44 45 Input 46 47 ``` 48 6 49 3 2 50 3 2 1 51 1 2 52 4 2 53 4 1 2 3 54 3 2 55 5 1 56 1 2 3 4 5 57 1 58 4 2 59 2 1 4 3 60 1 3 61 4 2 62 4 3 2 1 63 1 3 64 5 2 65 2 1 2 3 3 66 1 4 67 ``` 68 69 Output 70 71 ``` 72 YES 73 NO 74 YES 75 YES 76 NO 77 YES 78 ```