题意翻译

你在玩一种纸牌游戏。

牌有两种,一种是普通牌,使用它可以得到它的得分;另一种是加倍牌,使用它不但可以得到它的得分,还可以让排在它后面的牌的得分 $\times 2$。

一组牌的使用顺序可以任意,其得分为每一张牌的得分之和。

现在有两种操作,每一次操作形如 opt d

其中,$opt$ 代表牌的类型($1$ 为加倍牌,$0$ 为普通牌)。

而 $d$ 的正负代表操作类型,若 $d > 0$ ,代表你抽到了一张得分为 $d$ 的牌;反之,代表你丢弃了一张得分为 $|d|$ 的牌(丢弃纸牌不会得分)。

请回答每次操作后可能得到的最大得分


输入格式

第一行一个整数 $n$ ,表示总操作次数。

之后 $n$ 行,每行两个整数 $opt$ , $d$ ,意义同上。

保证不会同时有两张 $d$ 相同的纸牌


输出格式

输出 $n$ 行,每行一个整数,表示该操作后可能得到的最大得分。


Input & Output ‘s examples

Input ‘s eg

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

Output ‘s eg

5
25
10
15
36
21

数据范围和约定

对于 $100\%$ 的数据,保证 $1 \leq n \leq 2 \times 10^5$,$-10^9 \leq d \leq 10^9$,$opt ∈ \lbrack 0 , 1 \rbrack$。


分析

$\text{set}$ 练手题。

先说一个众所周知的事实,$\text{Codeforces}$ 的 $\text{Div 2} \text{D , E}$ 如果要支持插入删除一般都是 $\text{set}$ 因为别的真的没得考了……

现在回到这道题上。对于这道题,我们先考虑一下不带修的时候怎么做。

设 $k$ 为加倍牌的数量,有一个显然的想法就是将 $d$ 最大的 $k$ 张牌加倍。

但需要特判最大的 $k$ 张牌都是加倍牌的情况。对此,我们需要从不加倍的牌中找一个最大的替换掉加倍牌中最小的。

之后考虑如何带修。我们需要维护的东西有:加倍牌的数目,牌的类型与价值。

对此,我们可以开两个 $\text{set}$ ,一个维护前 $k$ 大,另一个维护剩下的牌。

剩下的就是细节问题了。


Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
char c = getchar(), f = 0; x = 0;
while (!isdigit(c)) f = (c == '-'), c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
x = f ? -x : x;
}

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 998244353;

ll n;
set<PLL> big , small;
ll smb , sma , smk , k;

int main() {
#ifdef LOCAL
freopen("try.in" , "r" , stdin);
freopen("try1.out" , "w" , stdout);
#endif
read(n);
ll now = 0;
rep(i , 1 , n){
ll opt , d;
read(opt) , read(d);
if(d > 0){
now += opt;
if(small.empty() || d >= small.rbegin()->fi){
big.insert(MP(d , opt));
smb += d;
if(opt == 1) smk += 1;
}
else{
small.insert(MP(d , opt));
sma += d;
}
}
else{
now -= opt , d = -d;
if(big.count(MP(d , opt))){
big.erase(big.find(MP(d , opt)));
smb -= d;
if(opt == 1) smk -= 1;
}
else{
small.erase(small.find(MP(d , opt)));
sma -= d;
}
}
if(big.size() > now){
small.insert(*big.begin());
smb -= big.begin()->fi;
sma += big.begin()->fi;
if(big.begin()->se == 1) smk -= 1;
big.erase(big.begin());
}
else if(big.size() < now){
big.insert(*small.rbegin());
sma -= small.rbegin()->fi;
smb += small.rbegin()->fi;
if(small.rbegin()->se == 1) smk += 1;
small.erase(--small.end());
}
ll res = 0;
if(smk != now || now == 0){
res = smb * 2 + sma;
}
else{
if(small.empty()){
res = smb * 2 + sma - big.begin()->fi;
}
else{
res = smb * 2 + sma - big.begin()->fi + small.rbegin()->fi;
}
}
printf("%lld\n" , res);
}

return 0;
}

THE END