F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
大视野在线测评-欢迎您
[ New Thread ]
Problem 1208 >> TLE 了,大佬们能帮我看看吗
lzjsy @ 2019-12-20 19:01:21
[ Quote ] [ Edit ] [ Delete ] 1#
#include<bits/stdc++.h>
using namespace std;
const int N=1000010,inf=0x3f3f3f3f,mod=1000000;
int siz[N],cnt[N],val[N],son[N][2],fa[N];
int n,rt,idx,qq,hj,a,b,fu,ypj;
long long ans;
void update(int x){
siz[x]=cnt[x]+siz[son[x][1]]+siz[son[x][0]];
}
void rotate(int x){
int y=fa[x],z=fa[y],o=(son[y][1]==x);
son[y][o]=son[x][o^1],fa[son[x][o^1]]=y;
son[x][o^1]=y,fa[y]=x;
son[z][son[z][1]==y]=x,fa[x]=z;
update(y),update(x);
}
void clear(int x){
int y=fa[x];
fa[x]=0;
son[y][1]==x?son[y][1]=0:son[y][0]=0;
}
void splay(int x){
for(register int y;(y=fa[x]);rotate(x)){
if(!fa[y]) continue;
rotate((son[fa[x]][1]==x)==(son[fa[y]][1]==y)?y:x);
}
rt=x;
}
void insert(int x,int a){
int y=0;
while(x&&val[x]!=a) y=x,x=son[x][a>val[x]];
if(x) cnt[x]++,siz[x]++;
else{
x=++idx,siz[x]=cnt[x]=1,val[x]=a;
fa[x]=y,son[y][a>val[y]]=x;
}
splay(x);
}
void del(int x){
splay(x);
if(cnt[x]>1){cnt[x]--,siz[x]--;return;}
rt=son[x][1];int mov=son[x][0],y=0,now=rt;
clear(son[x][1]),clear(son[x][0]);
while(now){
y=now,siz[now]+=siz[mov];
now=son[x][0];
}
fa[mov]=y,son[y][0]=mov;
}
void pre(int x,int a){
if(!x)return;
while(x)
if(val[x]<a) qq=x,x=son[x][1];
else x=son[x][0];
}
void suc(int x,int a){
if(!x)return;
while(x)
if(val[x]>a) hj=x,x=son[x][0];
else x=son[x][1];
}
int get(int x,int a){
while(x){
if(val[x]==a){
splay(x);
return x;
}
x=son[x][a>val[x]];
}
}
int main()
{
scanf("%d",&n);
insert(rt,inf),insert(rt,-inf);
for(register int q1=1;q1<=n;q1++){
scanf("%d %d",&a,&b);
if(a==0) a=-1;
if(fu*a>=0) insert(rt,b);
else{
insert(rt,b);
ypj=get(rt,b);
pre(ypj,b),suc(ypj,b);
if(cnt[ypj]==1){
ans=(ans+min(b-val[qq],val[hj]-b))%mod;
del((b-val[qq]<=val[hj]-b)?qq:hj);
}
else del(ypj);
del(get(rt,b));
}
fu+=a;
}
printf("%lld\n",ans%mod);
return 0;
}
[Top] [Previous Page] [Next Page]

HOME Back