← 返回题目列表

Codeforces · 1852/F

F. 熊猫聚会

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

小熊猫来城里迎接它们的亲戚蓝熊猫了!该城镇由数轴建模。

熊猫们已经计划好了他们的聚会,但日程安排不断变化。您将获得 x t c 形式的 $$$q$$$ 更新。

- 如果 $$$c <​​ 0$$$,则意味着 $$$|c|$$$ 更多小熊猫在位置 $$$x$$$ 和时间 $$$t$$$ 处进入数轴。然后,在每个单位时间内,他们可以各自独立地在数轴上的任一方向上移动一个单位,或者根本不移动。
- 如果 $$$c > 0$$$,则意味着 $$$c$$$ 更多蓝熊猫在 $$$t$$$ 时刻检查红熊猫的 $$$x$$$ 位置。如果蓝熊猫在特定的地点和时间没有遇到红熊猫,它们就会沮丧地立即离开数轴。如果在某个位置上有一只红熊猫,同时有一只蓝熊猫检查该位置,则它们会形成友谊并离开数轴。每只小熊猫最多可以与一只蓝熊猫建立友谊,反之亦然。

更新将按非递减 $$$x$$$ 值的顺序给出。每次更新后,如果小熊猫根据上面输入(包括)此更新中给出的所有更新以最佳顺序移动,请打印最大友谊数。

小熊猫的移动顺序可能会在更新之间发生变化。

输入

第一行包含 $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) – 更新次数。

接下来的 $$$q$$$ 行中的第 $$$i$$$ 行由 $$$3$$$ 整数 $$$x_i$$$、$$$t_i$$$ 和 $$$c_i$$$ ($$$0 \leq x_i \leq 10^9$$$, $$$0 \leq t_i \leq 组成10^9$$$, $$$0 < |c_i| \leq 1000$$$) – 第 $$$i$$$ 次更新的描述。

保证 $$$x_i$$$ 将以非降序给出。

输出

每次更新后,打印可以形成的最大好友数量。

示例

输入 #1

5
0 6 3
4 2 -5
7 4 -6
10 5 100
10 8 7

输出 #1

0
3
3
3
10

输入 #2

5
0 6 3
4 2 -5
7 4 -6
10 5 100
11 8 7

输出 #2

0
3
3
3
9

输入 #3

7
0 8 6
2 7 -2
3 1 -6
5 3 -8
7 3 -3
8 0 -2
8 2 1

输出 #3

0
0
6
6
6
6
7

输入#4

4
0 0 -3
0 0 2
0 0 4
0 0 -10

输出#4

0
2
3
6

注意

在第一个示例中,每次更新后的好友数量可以优化如下:

1. $$$3$$$ 蓝熊猫现在在 $$$6$$$ 位置检查位置 $$$0$$$ 的红熊猫。哪里都没有小熊猫,所以也就没有友谊。
2. $$$5$$$小熊猫现在出现在位置$$$4$$$,时间$$$2$$$。 $$$4$$$ 的红熊猫可以在 $$$6$$$ 时间前往位置 $$$0$$$,其中 $$$3$$$ 可以与 $$$3$$$ 现有的蓝熊猫建立友谊。
3. $$$6$$$小熊猫现在出现在位置$$$7$$$,时间$$$4$$$。没有添加新的蓝色熊猫,因此最大好友数量仍然是$$$3$$$。
4. $$$100$$$蓝色熊猫现在出现在位置$$$10$$$,时间$$$5$$$。没有小熊猫可以在 $$$5$$$ 时联系到他们,因此不会创建新的友谊。
5. $$$7$$$蓝色熊猫现在出现在位置$$$10$$$,时间$$$8$$$。 $$$6$$$ 位置 $$$7$$$ 和时间 $$$4$$$ 的红熊猫,以及 $$$1$$$ 位置 $$$4$$$ 和时间 $$$2$$$ 的红熊猫,可以到达 $$$7$$$ 位置 $$$10$$$ 的蓝熊猫,时间 $$$8$$$,增加 $$$7$$$ 新友谊。这使得友谊总数达到 $$$10$$$。