RT, 只有 10 分, 数组开大开小都是 MLE 。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;
#define fore(i,now) for(reg int i=head[now];i;i=e[i].nxt)
#define fora(i,a,b,c) for(reg int i=a;i<=b;i+=c)
#define forb(i,a,b,c) for(reg int i=a;i>=b;i-=c)
#define uLL unsigned LL
#define INF 0x3f3f3f3f
#define LL long long
#define reg register
#define N 100000005
#define R read()
inline LL read(){
LL s=0, f=1; char c=getchar();
while(c<'0'||c>'9') { if(c=='-') f=-f; c=getchar(); }
while(c>='0'&&c<='9') s=(s<<3)+(s<<1)+(c^48), c=getchar();
return s*f;
}
struct SBT {
struct Value {
int bp, pr;
friend bool operator < (const Value &a, const Value &b)
{ return a.pr<b.pr; }
friend bool operator > (const Value &a, const Value &b)
{ return a.pr>b.pr; }
friend bool operator == (const Value &a, const Value &b)
{ return a.pr==b.pr; }
friend bool operator >= (const Value &a, const Value &b)
{ return a.pr>=b.pr; }
} t;
struct SBTNode {
Value val; int siz, lson, rson;
} tree[N];
int top, rot;
SBT(int rot, int top)
{ this->rot=rot, this->top=top; }
inline Value MakeValue(int bp, int pr){
Value var; var.bp=bp; var.pr=pr; return var;
}
inline void LRotate(int &x){
int y=tree[x].rson;
tree[x].rson=tree[y].lson;
tree[y].lson=x;
tree[y].siz=tree[x].siz;
tree[x].siz=tree[tree[x].lson].siz+tree[tree[x].rson].siz+1;
x=y;
}
inline void RRotate(int &x){
int y=tree[x].lson;
tree[x].lson=tree[y].rson;
tree[y].rson=x;
tree[y].siz=tree[x].siz;
tree[x].siz=tree[tree[x].lson].siz+tree[tree[x].rson].siz+1;
x=y;
}
void Maintain(int &x, int f){
if(!f){
if(tree[tree[tree[x].lson].lson].siz>tree[tree[x].rson].siz)
RRotate(x);
else if(tree[tree[tree[x].lson].rson].siz>tree[tree[x].rson].siz)
LRotate(tree[x].lson), RRotate(x);
else return ;
}else{
if(tree[tree[tree[x].rson].rson].siz>tree[tree[x].lson].siz)
LRotate(x);
else if(tree[tree[tree[x].rson].lson].siz>tree[tree[x].lson].siz)
RRotate(tree[x].rson), LRotate(x);
else return ;
}
Maintain(tree[x].lson, 0);
Maintain(tree[x].rson, 1);
Maintain(x, 0);
Maintain(x, 1);
}
void Insert(int &x, Value val){
if(!x){
x=++top;
tree[x].lson=tree[x].rson=0;
tree[x].val=val;
tree[x].siz=1;
return ;
}
++tree[x].siz;
if(val<tree[x].val) Insert(tree[x].lson, val);
else Insert(tree[x].rson, val);
Maintain(x, val>=tree[x].val);
}
Value SearchK(int &x, int k){
int r=tree[tree[x].lson].siz+1;
if(r==k) return tree[x].val;
if(r>=k) return SearchK(tree[x].lson, k);
return SearchK(tree[x].rson, k-r);
}
Value Erase(int &x, Value val){
Value vl; --tree[x].siz;
if((val==tree[x].val)||(val<tree[x].val&&!tree[x].lson)||(val>tree[x].val&&!tree[x].rson)){
vl=tree[x].val;
if(tree[x].lson&&tree[x].rson)
tree[x].val=Erase(tree[x].lson, MakeValue(tree[x].val.bp, tree[x].val.pr+1));
else x=tree[x].lson+tree[x].rson;
}
else if(val<tree[x].val) vl=Erase(tree[x].lson, val);
else vl=Erase(tree[x].rson, val);
return vl;
}
} sbt(0, 0);
int main(){
LL W=0, C=0;
while(true){
int op, w, c;
if((op=R)==-1) break;
if(op==1) W+=(w=R), C+=(c=R), sbt.Insert(sbt.rot, sbt.MakeValue(w, c));
if(op==2){
sbt.t=sbt.SearchK(sbt.rot, sbt.top);
W-=sbt.t.bp; C-=sbt.t.pr;
sbt.Erase(sbt.rot, sbt.t);
}
if(op==3){
sbt.t=sbt.SearchK(sbt.rot, 1);
W-=sbt.t.bp; C-=sbt.t.pr;
sbt.Erase(sbt.rot, sbt.t);
}
}
printf("%lld %lld", W, C);
return 0;
}