← 返回题目列表

Codeforces · 1824/A

A. 洛天依与秀

中文机器翻译题面 查看原题

有 $$$n$$$ 人参加有关 VOCALOID 的节目。他们将坐在一排座位上,从左到右编号为 $$$1$$$ 到 $$$m$$$。

$$$n$$$ 的人过来按顺序就座。每个人通过以下三种方式之一占据座位:

1. 坐在最左边已就座者左侧的座位上,或者如果座位 $$$1$$$ 已被占用,则离开演出。如果当前没有人坐在座位上,请坐$$$m$$$。
2. 坐在最右边已就座者右侧的座位上,或者如果座位 $$$m$$$ 已被占用,则离开演出。如果当前没有人坐在座位上,请坐在 $$$1$$$ 座位上。
3. 坐在编号为 $$$x_i$$$ 的座位上。如果这个座位被占用,则离开演出。

现在你想知道,如果你可以让人们以任意顺序进入演出,最多可以入座多少人?

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — 人数和座位数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$x_1, x_2, \ldots, x_n$$$ ($$$-2 \le x_i \le m$$$, $$$x_i \ne 0$$$),其中第 $$$i$$$ 描述了第 $$$i$$$ 个人占据座位的方式:

1. 如果$$$x_i=-1$$$,则第$$$i$$$人按第一种方式入座。
2. 如果$$$x_i=-2$$$,则第$$$i$$$人按第二种方式入座。
3. 如果 $$$x_i > 0$$$,则第 $$$i$$$ 人以第三种方式入座,即他想坐在编号为 $$$x_i$$$ 的座位上,或者如果座位被占用则离开演出。

保证所有测试用例的 $$$n$$$ 总和和 $$$m$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出一个整数——可以占用座位的最大人数。

示例

输入 #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

注意

在第一个测试用例中,所有人都想占据 $$$5$$$ 座位,因此只有 $$$1$$$ 人可以占据该座位。

在第二个测试用例中,我们可以按 $$$1, 2, 3, 4$$$ 的顺序让人们入座,然后除了最后一个人之外的所有人都可以入座。

在第三个测试用例中,我们可以让人们按以下顺序进入节目:

让第三人进来:

–––3–––

让第四个人进来:

–––34––

让第五个人进来:

–––345–

让第一个人进来:

––1345–

让第二个人进来:

–21345–

因此,所有 $$$5$$$ 的人都入座了。

在第五个测试用例中,我们可以按以下顺序让人们进入节目:

让第四个人进来:

––––4–

让第三人进来:

–––34–

让第六个人进来,他将离开演出,因为他以第三种方式占据了第三个座位,并且必须坐在 $$$4$$$ 座位上,但它已经被占用了:

–––34–

让第五个人进来:

––534–

让第一个人进来:

–1534–

让第二个人进来:

21534–

因此,$$$5$$$ 的人入座。

在第七个测试用例中,我们可以按以下顺序让人们进入节目:

让第三人进来:

3––––––

让第四个人进来:

34–––––

让第五个人进来:

345––––

让第六个人进来:

3456–––

让第一个人进来:

34561––

让第二个人进来,他会离开演出,因为他占据了第一条路,但$$$1$$$座位已被占用:

34561––

因此,$$$5$$$ 人入座。