codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```