← 返回题目列表

Codeforces · 1398/E

E. 两种法术

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

坡旅甲(再次)玩电脑游戏。在这款游戏中,他使用魔法咒语与怪物战斗。

法术有两种类型:力量之火法术 $$$x$$$ 对怪物造成 $$$x$$$ 伤害,力量闪电法术 $$$y$$$ 对怪物造成 $$$y$$$ 伤害,并使波利卡普施放的下一个法术伤害加倍。每个法术在每场战斗中只能施展一次,但坡旅甲可以按任意顺序施展它们。

例如,假设坡旅甲知道三个法术:力量火法术$$$5$$$、力量闪电法术$$$1$$$和力量闪电法术$$$8$$$。有 $$$6$$$ 方法来选择他施法的顺序:

- 第一,第二,第三。该命令造成 $$$5 + 1 + 2 \cdot 8 = 22$$$ 伤害;
- 第一,第三,第二。该命令造成 $$$5 + 8 + 2 \cdot 1 = 15$$$ 伤害;
- 第二,第一,第三。该命令造成 $$$1 + 2 \cdot 5 + 8 = 19$$$ 伤害;
- 第二,第三,第一。该命令造成 $$$1 + 2 \cdot 8 + 2 \cdot 5 = 27$$$ 伤害;
- 第三,第一,第二。该命令造成 $$$8 + 2 \cdot 5 + 1 = 19$$$ 伤害;
- 第三,第二,第一。该命令造成 $$$8 + 2 \cdot 1 + 2 \cdot 5 = 20$$$ 伤害。

最初,坡旅甲知道 $$$0$$$ 法术。他的咒语集会改变 $$$n$$$ 次,每次他要么学习一个新咒语,要么忘记一个已知的咒语。每次更改后,计算波利卡普使用他所知道的法术可能造成的最大伤害。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 咒语集的更改次数。

接下来的 $$$n$$$ 行包含两个整数 $$$tp$$$ 和 $$$d$$$ ($$$0 \le tp_i \le 1$$$; $$$-10^9 \le d \le 10^9$$$; $$$d_i \neq 0$$$) — 更改的描述。如果 $$$tp_i$$$ 等于 $$$0$$$,则波利卡普学习(或忘记)火咒语,否则他学习(或忘记)闪电咒语。

如果$$$d_i > 0$$$,则坡旅甲学习力量咒语$$$d_i$$$。否则,波利卡普会忘记一个具有 $$$-d_i$$$ 威力的咒语,并且可以保证他在改变之前就知道该咒语。

保证每次改变后波利卡普所知道的所有法术的威力都是不同的(波利卡普永远不会知道具有相同威力的两个法术)。

输出

每次更改后,打印波利卡普可以处理他当前法术集的最大伤害。

示例

输入 #1

6
1 5
0 10
1 -5
0 5
1 11
0 -10

输出 #1

5
25
10
15
36
21