← 返回题目列表

Codeforces · 1463/C

C. 忙碌的机器人

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

你有一个可以沿着数轴移动的机器人。在$$$0$$$时刻,它位于$$$0$$$点。

您向机器人发出 $$$n$$$ 命令:在 $$$t_i$$$ 秒处,您命令机器人前往点 $$$x_i$$$。每当机器人收到命令时,它就会开始以每秒$$$1$$$单位的速度向点$$$x_i$$$移动,并在到达该点时停止。然而,当机器人移动时,它会忽略你给他的所有其他命令。

例如,假设您向机器人发出三个命令:在时间 $$$1$$$ 移动到点 $$$5$$$,在时间 $$$3$$$ 移动到点 $$$0$$$,在时间 $$$6$$$ 移动到点 $$$4$$$。然后机器人站在$$$0$$$直到时间$$$1$$$,然后开始向$$$5$$$移动,忽略第二个命令,在$$$6$$$时间到达$$$5$$$并立即开始移动到$$$4$$$以执行第三个命令。在时间 $$$7$$$ 达到 $$$4$$$ 并停在那里。

当机器人位于点 $$$x_i$$$ 时,如果在 $$$[t_i, t_{i + 1}]$$$ 范围内(即在发出此命令之后和发出另一个命令之前,包括两个边界;我们认为 $$$t_{n + 1} = +\infty$$$)内有一个时间点,则称命令 $$$i$$$ 成功。计算成功命令的数量。请注意,被忽略的命令有可能成功。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。接下来的几行描述了测试用例。

测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 命令数量。

接下来的 $$$n$$$ 行描述命令。这些行中的第 $$$i$$$ 包含两个整数 $$$t_i$$$ 和 $$$x_i$$$ ($$$1 \le t_i \le 10^9$$$, $$$-10^9 \le x_i \le 10^9$$$) — 第 $$$i$$$ 命令的时间和点。

命令按时间排序,即对于所有可能的 $$$i$$$,$$$t_i < t_{i + 1}$$$。

测试用例 $$$n$$$ 的总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出一个整数——成功命令的数量。

示例

输入 #1

8
3
1 5
3 0
6 4
3
1 5
2 4
10 -5
5
2 -5
3 1
4 1
5 1
6 1
4
3 3
5 -3
9 2
12 0
8
1 1
2 -6
7 2
8 3
12 -9
14 2
18 -1
23 9
5
1 -4
4 -7
6 -1
7 -3
8 -7
2
1 2
2 -2
6
3 10
5 5
8 0
12 -4
14 -7
19 -5

输出 #1

1
2
0
2
1
1
0
2

注意

问题陈述中描述了第一个测试用例中机器人的运动。只有最后一个命令成功。

在第二个测试用例中,第二个命令成功:机器人在时间 $$$5$$$ 通过目标点 $$$4$$$。另外,最后一个命令最终成功了。

在第三个测试用例中,没有命令成功,机器人在 $$$7$$$ 时刻停在 $$$-5$$$ 处。

以下是示例中每个测试用例每秒机器人位置的 $$$0$$$ 索引序列。剪切后所有位置都等于最后一个:

1.$$$[0, 0, 1, 2, 3, 4, 5, 4, 4, \点]$$$
2. $$$[0, 0, 1, 2, 3, 4, 5, 5, 5, 5, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -5, \点]$$$
3.$$$[0, 0, 0, -1, -2, -3, -4, -5, -5, \点]$$$
4.$$$[0, 0, 0, 0, 1, 2, 3, 3, 3, 3, 2, 2, 2, 1, 0, 0, \点]$$$
5. $$$[0, 0, 1, 0, -1, -2, -3, -4, -5, -6, -6, -6, -6, -7, -8, -9, -9, -9, -9, -8, -7, -6, -5, -4, -3, -2, -1, -1, \点]$$$
6.$$$[0, 0, -1, -2, -3, -4, -4, -3, -2, -1, -1, \点]$$$
7.$$$[0, 0, 1, 2, 2, \点]$$$
8. $$$[0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6, -7, -7, \点]$$$