#include<iostream>
#include<cmath>
#include<cstdio>
#define maxn 100001
#define mod  1000000
#define INF  2147483647
using namespace std;
struct Splay{ int fa,son[2],val,siz,cnt; }s1[maxn],s2[maxn]; // s1:pet s2:volunteer
int n,root1,root2,tot,ans;
void update(int crl,int x){
	if (crl==1) s1[x].siz=s1[s1[x].son[0]].siz+s1[s1[x].son[1]].siz+s1[x].cnt;
	else s2[x].siz=s2[s2[x].son[0]].siz+s2[s2[x].son[1]].siz+s1[x].cnt; 
}  
void rotate(int crl,int x){ // crl表示要操作的树。
	if (crl==1){
		int fa=s1[x].fa,gfa=s1[fa].fa,k=(s1[fa].son[1]==x);
		s1[gfa].son[s1[gfa].son[1]==fa]=x,s1[x].fa=gfa,s1[fa].fa=x,
		s1[fa].son[k]=s1[x].son[k^1],s1[s1[x].son[k^1]].fa=fa,
		s1[x].son[k^1]=fa;
		update(1,fa);update(1,x);
	}
	else {
		int fa=s2[x].fa,gfa=s2[fa].fa,k=(x==s2[fa].son[1]);
		s2[gfa].son[s2[gfa].son[1]==fa]=x,s2[x].fa=gfa,s2[fa].fa=x;
		s2[fa].son[k]=s2[x].son[k^1],s2[s2[x].son[k^1]].fa=fa,
		s2[x].son[k^1]=fa;
		update(2,fa);update(2,x);
	}
}
void splay(int crl,int x,int goal){
	int gfa,fa;
	if (crl==1){
		while (goal!=s1[x].fa){
			fa=s1[x].fa,gfa=s1[fa].fa;
			if (gfa!=goal){
				((s1[gfa].son[0]==fa) ^ (s1[fa].son[0]==x))?rotate(crl,x):rotate(crl,fa);
			} 
			rotate(crl,x);
		}
		if (goal==0) root1=x;
	}
	else {
		while (goal!=s2[x].fa){
			fa=s2[x].fa,gfa=s2[fa].fa;
			if (gfa!=goal){
				((s2[gfa].son[0]==fa) ^ (s2[fa].son[0]==x))?rotate(crl,x):rotate(crl,fa);
			}
			rotate(crl,x);
		}
		if (goal==0) root2=x;
	}
} 
void insert(int crl,int x){
	if (crl==1){
		int u=root1,fa=0;
		while (s1[u].val!=x&&u){
			fa=u,u=s1[u].son[x>s1[u].val];
		}
		if (u) s1[u].cnt++;
		else {
			u=++tot,s1[u].val=x,s1[u].siz=s1[u].cnt=1,s1[u].fa=fa,s1[u].son[1]=s1[u].son[0]=0;
			if (fa) s1[fa].son[x>s1[fa].val]=u; // 这句话别漏了 
		}
		splay(crl,u,0);
	}
	else {
		int u=root2,fa=0;
		while (s2[u].val!=x&&u){
			fa=u,u=s2[u].son[x>s2[u].val];
		}
		if (u) s2[u].cnt++;
		else {
			u=++tot,s2[u].val=x,s2[u].siz=s2[u].cnt=1,s2[u].fa=fa,s2[u].son[1]=s2[u].son[0]=0;
			if (fa) s2[fa].son[x>s2[fa].val]=u;
		}
		splay(crl,u,0);
	}
} 
void find(int crl,int x){
	if (crl==1){
		if (!root1) return;
		int u=root1;
		while (s1[u].val!=x&&s1[u].son[x>s1[u].val]){
			u=s1[u].son[x>s1[u].val];
		}
		splay(crl,u,0);
	}
	else {
		if (!root2) return;
		int u=root2;
		while (s2[u].val!=x&&s2[u].son[x>s2[u].val]){
			u=s2[u].son[x>s2[u].val];
		}
		splay(crl,u,0);
	}
}
int prenode(int crl,int x){
	find(crl,x);
	if (crl==1){
		if (s1[root1].val<x) return root1; // 注意 
		int u=s1[root1].son[0];
		if (!u) return 0;
		while (s1[u].son[1]){
			u=s1[u].son[1];
		}
		return u;
	}
	else {
		if (s2[root2].val<x) return root2;
		int u=s2[root2].son[0];
		if (!u) return 0;
		while (s2[u].son[1]){
			u=s2[u].son[1];
		}
		return u;
	}
}
int sufnode(int crl,int x){
	find(crl,x);
	if (crl==1){
		if (s1[root1].val>x) return root1; // 注意 
		int u=s1[root1].son[1];
		if (!u) return 0;
		while (s1[u].son[0]){
			u=s1[u].son[0];
		}
		return u;
	}
	else {
		if (s2[root2].val>x) return root2;
		int u=s2[root2].son[1];
		if (!u) return 0;
		while (s2[u].son[0]){
			u=s2[u].son[0];
		}
		return u;
	}	
}
void del(int crl,int x){
	int pre=prenode(crl,x),suf=sufnode(crl,x);
	splay(crl,pre,0);/*注意前一句*/splay(crl,suf,pre);
	if (crl==1){
		if (s1[s1[suf].son[0]].cnt>1){
			s1[s1[suf].son[0]].cnt--; splay(crl,s1[suf].son[0],0);
		}
		else s1[suf].son[0]=0;
	}
	else {
		if (s2[s2[suf].son[0]].cnt>1){
			s2[s2[suf].son[0]].cnt--; splay(crl,s2[suf].son[0],0);
		}
		else s2[suf].son[0]=0;
	}
}
int main(){
	freopen("pet8.in","r",stdin);
	freopen("2286程序.out","w",stdout);
//	ios::sync_with_stdio(false);
//	cin.tie(0); cout.tie(0);
	cin>>n; int a,b,now=0,a1,a2,a3; // now 为负数时：宠物多，为正数时，人多 a1,a2,a3:前驱 后继 根植 
	insert(1,INF),insert(1,-INF),insert(2,INF),insert(2,-INF); 
	for (int i=1;i<=n;i++){
		cin>>a>>b;
		if (a==0){
			if (now>0){ // 此时宠物找主人 
				a1=s2[prenode(2,b)].val,a2=s2[sufnode(2,b)].val,a3=s2[root2].val;
				if (a3==b){ del(2,b); } // 完全符合要求
				else {
					if (abs(a1-b)<=abs(a2-b)){ ans=(ans+abs(a1-b))%mod; del(2,a1); }
					else { ans=(ans+abs(a2-b))%mod; del(2,a2); }
				} 
			}
			else { insert(1,b); }
			now--;
		}
		else{
			if (now<0){ // 此时主人找宠物 
				a1=s1[prenode(1,b)].val,a2=s1[sufnode(1,b)].val,a3=s1[root1].val;
				if (a3==b){ del(1,a3); } // 完全符合要求
				else {
					if (abs(a1-b)<=abs(a2-b)){ ans=(ans+abs(a1-b))%mod; del(1,a1); }
					else { ans=(ans+abs(a2-b))%mod; del(1,a2); }
				} 
			}
			else { insert(2,b); }
			now++;
		}
//		cout<<endl<<"ans:"<<ans<<endl;
	}
	cout<<ans;
	return 0;
}

思路是用两棵 splay，TLE90pts，悬赏 2 关注