记录编号	489434	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 宠物收养所	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.386 s
提交时间	2018-03-02 15:02:07	内存使用	1.29 MiB

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int inf=8e4+10;
const int mod=1e6;
const double alpha=0.75;
LL ans;
int ls[inf],rs[inf],siz[inf],val[inf];
int n,sz,rt;
int p[inf],cnt;
int flag=-1;
int id,f;
void update(int x){
	siz[x]=siz[ls[x]]+siz[rs[x]]+1;
}
int rebuild(int l,int r){
	if(l>r)return 0;
	int mid=(l+r)>>1;
	int x=p[mid];
	siz[x]=1;
	ls[x]=rebuild(l,mid-1);
	rs[x]=rebuild(mid+1,r);
	update(x);
	return x;
}
void insert(int &x,int y){
	if(!x){
		x=++sz;
		siz[x]=1;
		val[x]=y;
		return ;
	}
	if(y<val[x])insert(ls[x],y);
	else insert(rs[x],y);
	update(x);
	if(max(siz[ls[x]],siz[rs[x]])>alpha*siz[x])id=x;
	if(ls[x]==id || rs[x]==id)f=x;
}
void dfs(int x){
	if(ls[x])dfs(ls[x]);
	p[++cnt]=x;
	if(rs[x])dfs(rs[x]);
}
void work(int x){
	id=-1;
	insert(rt,x);
	if(id!=-1){
		if(id==rt)f=0;
		cnt=0;
		dfs(id);
		int u=rebuild(1,cnt);
		if(ls[f]==id)ls[f]=u;
		else if(rs[f]==id)rs[f]=u;
		else rt=u;
	}
}
void del(int &x,int y){
	if(val[x]==y){
		if((!ls[x]) && (!rs[x]))x=0;
		else if(!ls[x])x=rs[x];
		else if(!rs[x])x=ls[x];
		else {
			int tmp=ls[x];
			while(rs[tmp])tmp=rs[tmp];
			val[x]=val[tmp];
			del(ls[x],val[x]);
			update(x);
		}
		return ;
	}
	if(y<val[x])del(ls[x],y);
	else del(rs[x],y);
	update(x);
}
int pre(int x,int y,int Max){
	if(!x)return Max;
	if(val[x]<=y){
		Max=max(Max,val[x]);
		return pre(rs[x],y,Max);
	}
	else return pre(ls[x],y,Max);
}
int succ(int x,int y,int Min){
	if(!x)return Min;
	if(val[x]>=y){
		Min=min(Min,val[x]);
		return succ(ls[x],y,Min);
	}
	else return succ(rs[x],y,Min);
}
int main()
{
	freopen("pet.in","r",stdin);
	freopen("pet.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		if(flag==-1){
			work(y);
			flag=x;
		}
		else if(flag==x){
			work(y);
		}
		else {
			int tmp1=pre(rt,y,-0x3fffffff),tmp2=succ(rt,y,0x3fffffff);
			if(tmp2-y<y-tmp1){
				del(rt,tmp2);
				ans+=tmp2-y;
				ans%=mod;
			}
			else {
				del(rt,tmp1);
				ans+=y-tmp1;
				ans%=mod;
			}
			if(!siz[rt])flag=-1;
		}
	}
	printf("%lld\n",ans);
	return 0;
}