1824A.md (5185B)
1 Source: https://codeforces.com/problemset/problem/1824/A 2 3 A. LuoTianyi and the Show 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 There are $n$ people taking part in a show about VOCALOID. They will sit in the row of seats, numbered $1$ to $m$ from left to right. 22 23 The $n$ people come and sit in order. Each person occupies a seat in one of three ways: 24 25 1. Sit in the seat next to the left of the leftmost person who is already sitting, or if seat $1$ is taken, then leave the show. If there is no one currently sitting, sit in seat $m$. 26 2. Sit in the seat next to the right of the rightmost person who is already sitting, or if seat $m$ is taken, then leave the show. If there is no one currently sitting, sit in seat $1$. 27 3. Sit in the seat numbered $x_i$. If this seat is taken, then leave the show. 28 29 Now you want to know what is the maximum number of people that can take a seat, if you can let people into the show in any order? 30 31 Input 32 33 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of test cases follows. 34 35 The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 10^5$) — the number of people and the number of seats. 36 37 The second line of each test case contains $n$ integers $x_1, x_2, \ldots, x_n$ ($-2 \le x_i \le m$, $x_i \ne 0$), the $i$-th of which describes the way in which the $i$-th person occupies a seat: 38 39 1. If $x_i=-1$, then $i$-th person takes the seat in the first way. 40 2. If $x_i=-2$, then $i$-th person takes the seat in the second way. 41 3. If $x_i \gt 0$, then the $i$-th person takes a seat in the third way, i.e. he wants to sit in the seat with the number $x_i$ or leave the show if it is occupied.. 42 43 It is guaranteed that sum of $n$ and the sum of $m$ over all test cases don't exceed $10^5$. 44 45 Output 46 47 For each test case output a single integer — the maximum number of people who can occupy a seat. 48 49 Example 50 51 Input 52 53 ``` 54 10 55 56 3 10 57 58 5 5 5 59 60 4 6 61 62 1 -2 -2 1 63 64 5 7 65 66 -1 -1 4 -2 -2 67 68 6 7 69 70 5 -2 -2 -2 -2 -2 71 72 6 6 73 74 -1 1 4 5 -1 4 75 76 6 8 77 78 -1 -1 -1 3 -1 -2 79 80 6 7 81 82 5 -1 -2 -2 -2 -2 83 84 3 1 85 86 -2 -2 1 87 88 2 5 89 90 5 -2 91 92 1 2 93 94 -1 95 ``` 96 97 Output 98 99 ``` 100 1 101 3 102 5 103 6 104 5 105 5 106 5 107 1 108 2 109 1 110 ``` 111 112 Note 113 114 In the first test case, all the people want to occupy the $5$ seat, so only $1$ people can occupy the seat. 115 116 In the second test case, we can let people in order $1, 2, 3, 4$, then all but the last person can take a seat. 117 118 In the third test case, we can let people into the show in that order: 119 120 Let the third person in: 121 122 | | | | | | | | 123 | --- | --- | --- | --- | --- | --- | --- | 124 | – | – | – | 3 | – | – | – | 125 126 Let the fourth person in: 127 128 | | | | | | | | 129 | --- | --- | --- | --- | --- | --- | --- | 130 | – | – | – | 3 | 4 | – | – | 131 132 Let the fifth person in: 133 134 | | | | | | | | 135 | --- | --- | --- | --- | --- | --- | --- | 136 | – | – | – | 3 | 4 | 5 | – | 137 138 Let the first person in: 139 140 | | | | | | | | 141 | --- | --- | --- | --- | --- | --- | --- | 142 | – | – | 1 | 3 | 4 | 5 | – | 143 144 Let the second person in: 145 146 | | | | | | | | 147 | --- | --- | --- | --- | --- | --- | --- | 148 | – | 2 | 1 | 3 | 4 | 5 | – | 149 150 Thus, all $5$ people took seats. 151 152 In the fifth test case, we can let people into the show in this order: 153 154 Let the fourth person in: 155 156 | | | | | | | 157 | --- | --- | --- | --- | --- | --- | 158 | – | – | – | – | 4 | – | 159 160 Let the third person in: 161 162 | | | | | | | 163 | --- | --- | --- | --- | --- | --- | 164 | – | – | – | 3 | 4 | – | 165 166 Let the sixth person in, he'll leave the show because he takes the third seat the third way and has to sit in the $4$ seat, but it's already taken: 167 168 | | | | | | | 169 | --- | --- | --- | --- | --- | --- | 170 | – | – | – | 3 | 4 | – | 171 172 Let the fifth person in: 173 174 | | | | | | | 175 | --- | --- | --- | --- | --- | --- | 176 | – | – | 5 | 3 | 4 | – | 177 178 Let the first person in: 179 180 | | | | | | | 181 | --- | --- | --- | --- | --- | --- | 182 | – | 1 | 5 | 3 | 4 | – | 183 184 Let the second person in: 185 186 | | | | | | | 187 | --- | --- | --- | --- | --- | --- | 188 | 2 | 1 | 5 | 3 | 4 | – | 189 190 Thus, $5$ of people took seats. 191 192 In the seventh test case, we can let people into the show in this order: 193 194 Let the third person in: 195 196 | | | | | | | | 197 | --- | --- | --- | --- | --- | --- | --- | 198 | 3 | – | – | – | – | – | – | 199 200 Let the fourth person in: 201 202 | | | | | | | | 203 | --- | --- | --- | --- | --- | --- | --- | 204 | 3 | 4 | – | – | – | – | – | 205 206 Let the fifth person in: 207 208 | | | | | | | | 209 | --- | --- | --- | --- | --- | --- | --- | 210 | 3 | 4 | 5 | – | – | – | – | 211 212 Let the sixth person in: 213 214 | | | | | | | | 215 | --- | --- | --- | --- | --- | --- | --- | 216 | 3 | 4 | 5 | 6 | – | – | – | 217 218 Let the first person in: 219 220 | | | | | | | | 221 | --- | --- | --- | --- | --- | --- | --- | 222 | 3 | 4 | 5 | 6 | 1 | – | – | 223 224 Let the second person in, he will leave the show because he occupies the first way, but the $1$ seat is taken: 225 226 | | | | | | | | 227 | --- | --- | --- | --- | --- | --- | --- | 228 | 3 | 4 | 5 | 6 | 1 | – | – | 229 230 Thus, $5$ people took seats.