题解
直接用平衡树模拟即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
using namespace std;
typedef long long ll;
struct Tr{
Tr *ch[2];
int r,v,siz,cnt;
int cmp(int x) const {
if(x==v)return -1;
return x>v;
}
void maintain(){
siz=cnt;
if(ch[0]!=NULL)siz+=ch[0]->siz;
if(ch[1]!=NULL)siz+=ch[1]->siz;
}
};
Tr tree[400005];
int n,S=0,ans,ANS=0;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
void rorate_tr(Tr* &tr,int d){
Tr *k=tr->ch[d^1];
tr->ch[d^1]=k->ch[d];
k->ch[d]=tr;
tr->maintain(),k->maintain(),tr=k;
}
void insert_tr(Tr* &tr,int x){
if(tr==NULL){
S++,tr=&tree[S],tr->siz=1,tr->cnt=1,tr->v=x;
tr->ch[0]=tr->ch[1]=NULL,tr->r=rand();
return ;
}
tr->siz++;
if(tr->v==x){
tr->cnt++;
}else{
int d=tr->cmp(x);
insert_tr(tr->ch[d],x);
if(tr->ch[d]->r>tr->r)rorate_tr(tr,d^1);
}
}
void del(Tr* &tr,int x){
int d=tr->cmp(x);
if(d==-1){
if(tr->cnt>1)tr->siz--,tr->cnt--;
else{
if(tr->ch[0]==NULL)tr=tr->ch[1];
else if(tr->ch[1]==NULL)tr=tr->ch[0];
else{
int d_=(tr->ch[0]->r>tr->ch[1]->r);
rorate_tr(tr,d_),tr->siz--,del(tr->ch[d_],x);
}
}
}else tr->siz--,del(tr->ch[d],x);
}
void previous(Tr *tr,int x){
if(tr==NULL)return ;
if(x>tr->v)
ans=tr->v,previous(tr->ch[1],x);
else previous(tr->ch[0],x);
}
void success(Tr *tr,int x){
if(tr==NULL)return ;
if(x<tr->v)
ans=tr->v,success(tr->ch[0],x);
else success(tr->ch[1],x);
}
void solve(){
n=read();
Tr *root=NULL;
int cnt1=0,cnt2=0,a,b;
for(int i=1;i<=n;i++){
a=read(),b=read();
if(!a){
if(!cnt2)insert_tr(root,b),cnt1++;
else{
int ans1,ans2,res;
ans=-1,previous(root,b),ans1=ans;
ans=-1,success(root,b),ans2=ans;
if(ans1==-1)res=ans2;
else if(ans2==-1)res=ans1;
else if(ans2-b<b-ans1)res=ans2;
else res=ans1;
del(root,res),ANS+=abs(res-b),ANS%=1000000;
cnt2--;
}
}else{
if(!cnt1)insert_tr(root,b),cnt2++;
else{//有宠物
int ans1,ans2,res;
ans=-1,previous(root,b),ans1=ans;
ans=-1,success(root,b),ans2=ans;
if(ans1==-1)res=ans2;
else if(ans2==-1)res=ans1;
else if(ans2-b<b-ans1)res=ans2;
else res=ans1;
del(root,res),ANS+=abs(res-b),ANS%=1000000;
cnt1--;
}
}
}
printf("%d\n",ANS);
}
int main(){
solve();
return 0;
}