1980C.md (2944B)
1 Source: https://codeforces.com/problemset/problem/1980/C 2 3 C. Sofia and the Lost Operations 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 Sofia had an array of $n$ integers $a_1, a_2, \ldots, a_n$. One day she got bored with it, so she decided to sequentially apply $m$ modification operations to it. 22 23 Each modification operation is described by a pair of numbers $\langle c_j, d_j \rangle$ and means that the element of the array with index $c_j$ should be assigned the value $d_j$, i.e., perform the assignment $a_{c_j} = d_j$. After applying all modification operations sequentially, Sofia discarded the resulting array. 24 25 Recently, you found an array of $n$ integers $b_1, b_2, \ldots, b_n$. You are interested in whether this array is Sofia's array. You know the values of the original array, as well as the values $d_1, d_2, \ldots, d_m$. The values $c_1, c_2, \ldots, c_m$ turned out to be lost. 26 27 Is there a sequence $c_1, c_2, \ldots, c_m$ such that the sequential application of modification operations $\langle c_1, d_1, \rangle, \langle c_2, d_2, \rangle, \ldots, \langle c_m, d_m \rangle$ to the array $a_1, a_2, \ldots, a_n$ transforms it into the array $b_1, b_2, \ldots, b_n$? 28 29 Input 30 31 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 32 33 Then follow the descriptions of the test cases. 34 35 The first line of each test case contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of the array. 36 37 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the elements of the original array. 38 39 The third line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 10^9$) — the elements of the found array. 40 41 The fourth line contains an integer $m$ ($1 \le m \le 2 \cdot 10^5$) — the number of modification operations. 42 43 The fifth line contains $m$ integers $d_1, d_2, \ldots, d_m$ ($1 \le d_j \le 10^9$) — the preserved value for each modification operation. 44 45 It is guaranteed that the sum of the values of $n$ for all test cases does not exceed $2 \cdot 10^5$, similarly the sum of the values of $m$ for all test cases does not exceed $2 \cdot 10^5$. 46 47 Output 48 49 Output $t$ lines, each of which is the answer to the corresponding test case. As an answer, output "YES" if there exists a suitable sequence $c_1, c_2, \ldots, c_m$, and "NO" otherwise. 50 51 You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer). 52 53 Example 54 55 Input 56 57 ``` 58 7 59 60 3 61 62 1 2 1 63 64 1 3 2 65 66 4 67 68 1 3 1 2 69 70 4 71 72 1 2 3 5 73 74 2 1 3 5 75 76 2 77 78 2 3 79 80 5 81 82 7 6 1 10 10 83 84 3 6 1 11 11 85 86 3 87 88 4 3 11 89 90 4 91 92 3 1 7 8 93 94 2 2 7 10 95 96 5 97 98 10 3 2 2 1 99 100 5 101 102 5 7 1 7 9 103 104 4 10 1 2 9 105 106 8 107 108 1 1 9 8 7 2 10 4 109 110 4 111 112 1000000000 203 203 203 113 114 203 1000000000 203 1000000000 115 116 2 117 118 203 1000000000 119 120 1 121 122 1 123 124 1 125 126 5 127 128 1 3 4 5 1 129 ``` 130 131 Output 132 133 ``` 134 YES 135 NO 136 NO 137 NO 138 YES 139 NO 140 YES 141 ```