Treap100pts求条

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct str{
	int l,r,v,dat,cnt,size;
};
str a1[80005];
str a2[80005];
int tot1;
int tot2;
int root1;
int root2;
int newone1(int v){
	tot1++;
	a1[tot1].v=v;
	a1[tot1].dat=rand();
	a1[tot1].cnt=1;
	a1[tot1].size=1;
	return tot1;
}
int newone2(int v){
	tot2++;
	a2[tot2].v=v;
	a2[tot2].dat=rand();
	a2[tot2].cnt=1;
	a2[tot2].size=1;
	return tot2;
}
void update1(int p){
	a1[p].size=a1[a1[p].l].size+a1[a1[p].r].size+a1[p].cnt;
}
void update2(int p){
	a2[p].size=a2[a2[p].l].size+a2[a2[p].r].size+a2[p].cnt;
}
void zig1(int &p){
	int q=a1[p].l;
	a1[p].l=a1[q].r;
	a1[q].r=p;
	p=q;
	update1(a1[p].r);
	update1(p);
}
void zig2(int &p){
	int q=a2[p].l;
	a2[p].l=a2[q].r;
	a2[q].r=p;
	p=q;
	update2(a2[p].r);
	update2(p);
}
void zag1(int &p){
	int q=a1[p].r;
	a1[p].r=a1[q].l;
	a1[q].l=p;
	p=q;
	update1(a1[p].l);
	update1(p);
}
void zag2(int &p){
	int q=a2[p].r;
	a2[p].r=a2[q].l;
	a2[q].l=p;
	p=q;
	update2(a2[p].l);
	update2(p);
}
void build1(){
	root1=newone1(-0x7fffffff);
	a1[1].r=newone1(0x7fffffff);;
	update1(root1);
}
void build2(){
	root2=newone2(-0x7fffffff);
	a2[1].r=newone2(0x7fffffff);;
	update2(root2);
}
void insert1(int &p,int v){
	if(p==0){
		p=newone1(v);
		return;
	}
	if(v==a1[p].v){
		a1[p].cnt++;
		update1(p);
		return;
	}
	if(v<a1[p].v){
		insert1(a1[p].l,v);
		if(a1[p].dat<a1[a1[p].l].dat){
			zig1(p);
		}
	}
	if(v>a1[p].v){
		insert1(a1[p].r,v);
		if(a1[p].dat<a1[a1[p].r].dat){
			zag1(p);
		}
	}
	update1(p);
}
void insert2(int &p,int v){
	if(p==0){
		p=newone2(v);
		return;
	}
	if(v==a2[p].v){
		a2[p].cnt++;
		update2(p);
		return;
	}
	if(v<a2[p].v){
		insert2(a2[p].l,v);
		if(a2[p].dat<a2[a2[p].l].dat){
			zig2(p);
		}
	}
	if(v>a2[p].v){
		insert2(a2[p].r,v);
		if(a2[p].dat<a2[a2[p].r].dat){
			zag2(p);
		}
	}
	update2(p);
}
void remove1(int &p,int v){
	if(v==a1[p].v){
		if(a1[p].cnt!=1){
			a1[p].cnt--;
			update1(p);
			return;
		}
		if(a1[p].cnt==1){
			if(a1[p].l==0&&a1[p].r==0){
				p=0;	
			}
			else{
				if(a1[p].r==0||a1[a1[p].l].dat>a1[a1[p].r].dat){
					zig1(p);
					remove1(a1[p].r,v);
				}
				else{
					zag1(p);
					remove1(a1[p].l,v);
				}
				update1(p);
			}
		}
		return;
	}
	if(v<a1[p].v){
		remove1(a1[p].l,v);
	}
	if(v>a1[p].v){
		remove1(a1[p].r,v);
	}
	update1(p);
}
void remove2(int &p,int v){
	if(v==a2[p].v){
		if(a2[p].cnt!=1){
			a2[p].cnt--;
			update2(p);
			return;
		}
		if(a2[p].cnt==1){
			if(a2[p].l==0&&a2[p].r==0){
				p=0;	
			}
			else{
				if(a2[p].r==0||a2[a2[p].l].dat>a2[a2[p].r].dat){
					zig2(p);
					remove2(a2[p].r,v);
				}
				else{
					zag2(p);
					remove2(a2[p].l,v);
				}
				update2(p);
			}
		}
		return;
	}
	if(v<a2[p].v){
		remove2(a2[p].l,v);
	}
	if(v>a2[p].v){
		remove2(a2[p].r,v);
	}
	update2(p);
}
int qp1(int v){
	int p=root1;
	int ans;
	while(p!=0){
		if(a1[p].v<v){
			ans=a1[p].v;
			p=a1[p].r;
		}
		if(a1[p].v>=v){
			p=a1[p].l;
		}
	}
	return ans;
}
int qp2(int v){
	int p=root2;
	int ans;
	while(p!=0){
		if(a2[p].v<v){
			ans=a2[p].v;
			p=a2[p].r;
		}
		if(a2[p].v>=v){
			p=a2[p].l;
		}
	}
	return ans;
}
int qn1(int v){
	int p=root1;
	int ans;
	while(p!=0){
		if(a1[p].v>v){
			ans=a1[p].v;
			p=a1[p].l;
		}
		if(a1[p].v<=v){
			p=a1[p].r;
		}
	}
	return ans;
}
int qn2(int v){
	int p=root2;
	int ans;
	while(p!=0){
		if(a2[p].v>v){
			ans=a2[p].v;
			p=a2[p].l;
		}
		if(a2[p].v<=v){
			p=a2[p].r;
		}
	}
	return ans;
}
map<int,int>m1;
map<int,int>m2;
int ans;
int mod=1e6;
signed main(){
	//ios::sync_with_stdio(0);
	cin.tie(0);
	build1();
	build2();
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int a,b;
		cin>>a>>b;
		
		if(a==0){
			if(a1[root1].size>2){
				if(m1[b]>=1){
					m1[b]--;
					continue;
				}
				int pre1=qp1(b);
				int next1=qn1(b);
				if(abs(b-pre1)<=abs(b-next1)){
					ans+=abs(b-pre1);
					m1[pre1]--;
					remove1(root1,pre1);
				}
				else{
					ans+=abs(b-next1);
					m1[next1]--;
					remove1(root1,next1);
				}
			}
			else{
				m2[b]++;
				insert2(root2,b);
			}
		}
		if(a==1){
			if(a2[root2].size>2){
				if(m2[b]>=1){
					m2[b]--;
					continue;
				}
				int pre2=qp2(b);
				int next2=qn2(b);
				if(abs(b-pre2)<=abs(b-next2)){
					ans+=abs(b-pre2);
					m2[pre2]--;
					remove2(root2,pre2);
				}
				else{
					ans+=abs(b-next2);
					m2[next2]--;
					remove2(root2,next2);
				}
			}
			else{
				m1[b]++;
				insert1(root1,b);
			}
		}
	}
	cout<<ans%mod;
}