A15921. LuoTianyi and the Show
编程题
普及/提高-
知识点
题目描述
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.
The $n$ people come and sit in order. Each person occupies a seat in one of three ways:
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$ .
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$ .
3. Sit in the seat numbered $x_i$ . If this seat is taken, then leave the show.
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?
The $n$ people come and sit in order. Each person occupies a seat in one of three ways:
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$ .
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$ .
3. Sit in the seat numbered $x_i$ . If this seat is taken, then leave the show.
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?
输入格式
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.
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.
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:
1. If $x_i=-1$ , then $i$ -th person takes the seat in the first way.
2. If $x_i=-2$ , then $i$ -th person takes the seat in the second way.
3. If $x_i > 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..
It is guaranteed that sum of $n$ and the sum of $m$ over all test cases don't exceed $10^5$ .
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.
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:
1. If $x_i=-1$ , then $i$ -th person takes the seat in the first way.
2. If $x_i=-2$ , then $i$ -th person takes the seat in the second way.
3. If $x_i > 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..
It is guaranteed that sum of $n$ and the sum of $m$ over all test cases don't exceed $10^5$ .
输出格式
For each test case output a single integer — the maximum number of people who can occupy a seat.
输入输出样例
输入 #1
10 3 10 5 5 5 4 6 1 -2 -2 1 5 7 -1 -1 4 -2 -2 6 7 5 -2 -2 -2 -2 -2 6 6 -1 1 4 5 -1 4 6 8 -1 -1 -1 3 -1 -2 6 7 5 -1 -2 -2 -2 -2 3 1 -2 -2 1 2 5 5 -2 1 2 -1
输出 #1
1 3 5 6 5 5 5 1 2 1
说明/提示
In the first test case, all the people want to occupy the $5$ seat, so only $1$ people can occupy the seat.
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.
In the third test case, we can let people into the show in that order:
Let the third person in:
–––3–––Let the fourth person in:
–––34––Let the fifth person in:
–––345–Let the first person in:
––1345–Let the second person in:
–21345–Thus, all $5$ people took seats.
In the fifth test case, we can let people into the show in this order:
Let the fourth person in:
––––4–Let the third person in:
–––34–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:
–––34–Let the fifth person in:
––534–Let the first person in:
–1534–Let the second person in:
21534–Thus, $5$ of people took seats.
In the seventh test case, we can let people into the show in this order:
Let the third person in:
3––––––Let the fourth person in:
34–––––Let the fifth person in:
345––––Let the sixth person in:
3456–––Let the first person in:
34561––Let the second person in, he will leave the show because he occupies the first way, but the $1$ seat is taken:
34561––Thus, $5$ people took seats.
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.
In the third test case, we can let people into the show in that order:
Let the third person in:
–––3–––Let the fourth person in:
–––34––Let the fifth person in:
–––345–Let the first person in:
––1345–Let the second person in:
–21345–Thus, all $5$ people took seats.
In the fifth test case, we can let people into the show in this order:
Let the fourth person in:
––––4–Let the third person in:
–––34–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:
–––34–Let the fifth person in:
––534–Let the first person in:
–1534–Let the second person in:
21534–Thus, $5$ of people took seats.
In the seventh test case, we can let people into the show in this order:
Let the third person in:
3––––––Let the fourth person in:
34–––––Let the fifth person in:
345––––Let the sixth person in:
3456–––Let the first person in:
34561––Let the second person in, he will leave the show because he occupies the first way, but the $1$ seat is taken:
34561––Thus, $5$ people took seats.