codeforces-scrape

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

2248B.md (3069B)


      1 Source: https://codeforces.com/problemset/problem/2248/B
      2 
      3 B. Merge to Match
      4 
      5 time limit per test
      6 
      7 1.5 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 two arrays $a$ and $b$ of lengths $n$ and $m$, respectively. All $n + m$ integers in these arrays are distinct.
     22 
     23 You can perform the following operation on $a$ any number of times (possibly, zero):
     24 
     25 * Choose two elements of $a$ with values $x$ and $y$, where $x \le y$.
     26 * Delete these two elements from $a$.
     27 * Insert one integer $z$ into $a$ such that $x \le z \le y$.
     28 
     29 After performing all operations, you may arrange the elements of $a$ in any order.
     30 
     31 Determine whether it is possible to make $a$ equal to $b$.
     32 
     33 Input
     34 
     35 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     36 
     37 The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the lengths of the arrays $a$ and $b$.
     38 
     39 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).
     40 
     41 The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($1 \le b_i \le 10^9$).
     42 
     43 It is guaranteed that all $n + m$ integers in the arrays $a$ and $b$ are distinct.
     44 
     45 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     46 
     47 It is guaranteed that the sum of $m$ over all test cases does not exceed $2 \cdot 10^5$.
     48 
     49 Output
     50 
     51 For each test case, print "YES" if it is possible to make $a$ equal to $b$, and "NO" otherwise.
     52 
     53 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
     54 
     55 Example
     56 
     57 Input
     58 
     59 ```
     60 11
     61 
     62 2 1
     63 
     64 1 3
     65 
     66 2
     67 
     68 3 2
     69 
     70 1 3 5
     71 
     72 2 4
     73 
     74 4 2
     75 
     76 1 3 5 7
     77 
     78 4 6
     79 
     80 4 2
     81 
     82 2 5 8 11
     83 
     84 1 10
     85 
     86 4 2
     87 
     88 1 4 7 9
     89 
     90 3 10
     91 
     92 5 2
     93 
     94 10 1 100 6 4
     95 
     96 90 5
     97 
     98 6 3
     99 
    100 1 4 10 20 30 40
    101 
    102 3 15 35
    103 
    104 4 2
    105 
    106 1 2 3 100
    107 
    108 4 5
    109 
    110 7 3
    111 
    112 1 8 3 30 18 12 25
    113 
    114 2 15 28
    115 
    116 4 1
    117 
    118 1 2 3 5
    119 
    120 4
    121 
    122 4 2
    123 
    124 1 3 5 6
    125 
    126 2 4
    127 ```
    128 
    129 Output
    130 
    131 ```
    132 YES
    133 
    134 NO
    135 
    136 YES
    137 
    138 NO
    139 
    140 NO
    141 
    142 YES
    143 
    144 YES
    145 
    146 NO
    147 
    148 YES
    149 
    150 YES
    151 
    152 YES
    153 ```
    154 
    155 Note
    156 
    157 In the first test case, choose $1$ and $3$, delete them, and insert $2$.
    158 
    159 In the second test case, it can be shown that no sequence of operations can make $a$ equal to $b$.
    160 
    161 In the third test case, choose $1$ and $5$, delete them, and insert $4$. Then, choose $3$ and $7$, delete them, and insert $6$.
    162 
    163 In the sixth test case, first choose $1$ and $10$, delete them, and insert $5$. Next, choose $6$ and $100$, delete them, and insert $90$. Finally, choose $4$ and $5$, delete them, and insert $5$.
    164 
    165 In the seventh test case, for the pairs $(1,4)$, $(10,20)$, and $(30,40)$, delete both elements and insert $3$, $15$, and $35$, respectively.
    166 
    167 In the ninth test case, delete the pairs $(1,3)$, $(8,18)$, and $(25,30)$ and insert $2$, $15$, and $28$, respectively. Then, delete $12$ and $15$ and insert $15$.
    168 
    169 In the tenth test case, first choose $1$ and $2$, delete them, and insert $2$. Then, choose $2$ and $3$, delete them, and insert $3$. Finally, choose $3$ and $5$, delete them, and insert $4$.