codeforces-scrape

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

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.