Two Types of Spells

题意翻译

【题目描述】 你有许多咒语。 咒语可以被分为两种：火之咒和电之咒。 每一条咒语有一个初始攻击力。 众所周知，一连串咒语的总攻击力和它们释放的顺序是密切相关的。 对于一种释放顺序，设第`i`个释放的咒语的初始攻击力为$w_i$。那么，如果第`i-1`个释放的咒语为电之咒，则它最终产生的攻击力为$2\cdot w_i$，如果第`i-1`个释放的咒语为火之咒，则它最终产生的攻击力为$w_i$。 总攻击力即为所有咒语的最终攻击力之和。 作为一名魔法师，你会学习新的咒语，同时也会忘掉旧的咒语。 刚开始你不会任何咒语，为了评估自己的实力，你想知道在每一次学习或忘却后，对于所有可能的咒语释放顺序，总攻击力能达到的最大值是多少。 【输入格式】 第一行一个整数`n`（$1\leq n \leq 2\cdot 10^5$），表示你学习和忘却的总次数。 接下来`n`行，每行两个整数`tp`和`d`（$0\leq tp \leq 1$，$-10^9 \leq d \leq 10^9$，$d\neq 0$）。若`tp=0`，则表示你学习或忘却的咒语是火之咒，否则是电之咒。若`d<0`，则表示你忘记了一个初始攻击力为`-d`的咒语（保证这样的咒语在此时一定被学习了），否则表示你学习了一个初始攻击力为`d`的咒语。 你永远也不会知道两个初始攻击力相同的咒语。 【输出格式】 在每一次学习或忘却后，输出总攻击力能达到的最大值。

题目描述

Polycarp plays a computer game (yet again). In this game, he fights monsters using magic spells. There are two types of spells: fire spell of power $ x $ deals $ x $ damage to the monster, and lightning spell of power $ y $ deals $ y $ damage to the monster and doubles the damage of the next spell Polycarp casts. Each spell can be cast only once per battle, but Polycarp can cast them in any order. For example, suppose that Polycarp knows three spells: a fire spell of power $ 5 $ , a lightning spell of power $ 1 $ , and a lightning spell of power $ 8 $ . There are $ 6 $ ways to choose the order in which he casts the spells: - first, second, third. This order deals $ 5 + 1 + 2 \cdot 8 = 22 $ damage; - first, third, second. This order deals $ 5 + 8 + 2 \cdot 1 = 15 $ damage; - second, first, third. This order deals $ 1 + 2 \cdot 5 + 8 = 19 $ damage; - second, third, first. This order deals $ 1 + 2 \cdot 8 + 2 \cdot 5 = 27 $ damage; - third, first, second. This order deals $ 8 + 2 \cdot 5 + 1 = 19 $ damage; - third, second, first. This order deals $ 8 + 2 \cdot 1 + 2 \cdot 5 = 20 $ damage. Initially, Polycarp knows $ 0 $ spells. His spell set changes $ n $ times, each time he either learns a new spell or forgets an already known one. After each change, calculate the maximum possible damage Polycarp may deal using the spells he knows.

输入输出格式

输入格式

The first line contains one integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of changes to the spell set. Each of the next $ n $ lines contains two integers $ tp $ and $ d $ ( $ 0 \le tp_i \le 1 $ ; $ -10^9 \le d \le 10^9 $ ; $ d_i \neq 0 $ ) — the description of the change. If $ tp_i $ if equal to $ 0 $ , then Polycarp learns (or forgets) a fire spell, otherwise he learns (or forgets) a lightning spell. If $ d_i > 0 $ , then Polycarp learns a spell of power $ d_i $ . Otherwise, Polycarp forgets a spell with power $ -d_i $ , and it is guaranteed that he knew that spell before the change. It is guaranteed that the powers of all spells Polycarp knows after each change are different (Polycarp never knows two spells with the same power).

输出格式

After each change, print the maximum damage Polycarp can deal with his current set of spells.

输入输出样例

输入样例 #1

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

输出样例 #1

5
25
10
15
36
21