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$.