← 返回题目列表

Codeforces · 2025/G

G. 可变损坏

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

Monocarp 正在召集一支军队在电子游戏中与一条龙作战。

军队由两部分组成:英雄和防御神器。每个英雄都有一个参数——他的生命值。每件防御神器还有一个参数——耐用性。

在战斗开始之前,Monocarp会向英雄分发神器,以便每个英雄最多获得一件神器。

战斗由如下回合组成:

- 首先,龙对每个英雄造成等于 $$$\frac{1}{a + b}$$$(未经四舍五入的实数)的伤害,其中 $$$a$$$ 是存活英雄的数量,$$$b$$$ 是活动神器的数量;
- 之后,所有生命值为 $$$0$$$ 或更少的英雄死亡;
- 最后,一些工件被停用。当发生以下其中一种情况时,具有耐久度 $$$x$$$ 的神器将被停用:持有该神器的英雄死亡或受到 $$$x$$$ 总伤害(从战斗开始)。如果一件神器没有被任何英雄持有,那么它从战斗开始时就处于非活动状态。

当没有英雄活着时,战斗结束。

最初,军队是空的。有 $$$q$$$ 查询:向军队添加生命值 $$$x$$$ 的英雄或耐久性 $$$y$$$ 的神器。每次查询后,确定 Monocarp 在最佳分配工件的情况下可以生存的最大轮数。

输入

第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — 查询数。

在以下 $$$q$$$ 行的第 $$$i$$$ 行中,有两个整数 $$$t_i$$$ 和 $$$v_i$$$ ($$$t_i \in \{1, 2\}$$$; $$$1 \le v_i \le 10^9$$$) - 查询的类型和查询参数的值。如果类型为$$$1$$$,则添加生命值为$$$v_i$$$的英雄。如果类型为$$$2$$$,则添加具有耐用性$$$v_i$$$的工件。

输出

打印 $$$q$$$ 整数。每次查询后,输出 Monocarp 在最佳分配工件的情况下可以生存的最大轮数。

示例

输入 #1

3
2 5
1 4
1 10

输出 #1

0
8
19

输入 #2

10
1 9
1 6
2 4
1 8
1 3
2 10
1 3
1 6
1 10
2 6

输出 #2

9
15
19
27
30
39
42
48
59
65

注意

让我们考虑第一个例子。

- 添加了一件耐久度为 $$$5$$$ 的神器。由于还没有英雄,战斗立即结束。
- 添加了一名生命值为 $$$4$$$ 的英雄。 Monocarp 可以给他一件耐久度为 $$$5$$$ 的神器。首先,英雄在某些回合中会受到 $$$\frac{1}{1 + 1} = \frac{1}{2}$$$ 伤害。经过 $$$8$$$ 这样的回合后,总共会造成 $$$4$$$ 伤害,英雄将会死亡,而神器将会停用。没有更多的英雄活着,所以战斗在 $$$8$$$ 回合后结束。
- 添加了一名生命值为 $$$10$$$ 的英雄。现在就让耐久度$$$5$$$的神器和这个英雄在一起吧。然后,在前 $$$12$$$ 轮中,英雄将受到 $$$12 \cdot \frac{1}{2 + 1} = 4$$$ 伤害,第一个英雄将会死亡。第二个英雄还剩 $$$6$$$ 生命值,神器有 $$$1$$$ 耐久度。现在伤害为$$$\frac{1}{2}$$$,因此在另外$$$2$$$轮后,神器将停用。第二个英雄还剩下 $$$5$$$ 生命值。再过 $$$5$$$ 轮后,第二个英雄就会死亡。因此,答案是$$$12 + 2 + 5 = 19$$$。