1843E.md (2646B)
1 Source: https://codeforces.com/problemset/problem/1843/E 2 3 E. Tracking Segments 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$ consisting of $n$ zeros. You are also given a set of $m$ not necessarily different segments. Each segment is defined by two numbers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) and represents a subarray $a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$ of the array $a$. 22 23 Let's call the segment $l_i, r_i$ beautiful if the number of ones on this segment is strictly greater than the number of zeros. For example, if $a = [1, 0, 1, 0, 1]$, then the segment $[1, 5]$ is beautiful (the number of ones is $3$, the number of zeros is $2$), but the segment $[3, 4]$ is not is beautiful (the number of ones is $1$, the number of zeros is $1$). 24 25 You also have $q$ changes. For each change you are given the number $1 \le x \le n$, which means that you must assign an element $a_x$ the value $1$. 26 27 You have to find the first change after which at least one of $m$ given segments becomes beautiful, or report that none of them is beautiful after processing all $q$ changes. 28 29 Input 30 31 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 32 33 The first line of each test case contains two integers $n$ and $m$ ($1 \le m \le n \le 10^5$) — the size of the array $a$ and the number of segments, respectively. 34 35 Then there are $m$ lines consisting of two numbers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) —the boundaries of the segments. 36 37 The next line contains an integer $q$ ($1 \le q \le n$) — the number of changes. 38 39 The following $q$ lines each contain a single integer $x$ ($1 \le x \le n$) — the index of the array element that needs to be set to $1$. It is guaranteed that indexes in queries are distinct. 40 41 It is guaranteed that the sum of $n$ for all test cases does not exceed $10^5$. 42 43 Output 44 45 For each test case, output one integer — the minimum change number after which at least one of the segments will be beautiful, or $-1$ if none of the segments will be beautiful. 46 47 Example 48 49 Input 50 51 ``` 52 6 53 54 5 5 55 56 1 2 57 58 4 5 59 60 1 5 61 62 1 3 63 64 2 4 65 66 5 67 68 5 69 70 3 71 72 1 73 74 2 75 76 4 77 78 4 2 79 80 1 1 81 82 4 4 83 84 2 85 86 2 87 88 3 89 90 5 2 91 92 1 5 93 94 1 5 95 96 4 97 98 2 99 100 1 101 102 3 103 104 4 105 106 5 2 107 108 1 5 109 110 1 3 111 112 5 113 114 4 115 116 1 117 118 2 119 120 3 121 122 5 123 124 5 5 125 126 1 5 127 128 1 5 129 130 1 5 131 132 1 5 133 134 1 4 135 136 3 137 138 1 139 140 4 141 142 3 143 144 3 2 145 146 2 2 147 148 1 3 149 150 3 151 152 2 153 154 3 155 156 1 157 ``` 158 159 Output 160 161 ``` 162 3 163 -1 164 3 165 3 166 3 167 1 168 ``` 169 170 Note 171 172 In the first case, after first 2 changes we won't have any beautiful segments, but after the third one on a segment $[1; 5]$ there will be 3 ones and only 2 zeros, so the answer is 3. 173 174 In the second case, there won't be any beautiful segments.