记录编号	346078	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 宠物收养所	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.372 s
提交时间	2016-11-11 21:01:22	内存使用	1.98 MiB

#include<cstdio>
#include<climits>
using namespace std;
const int N=100010;
int n,l[N],r[N],s[N],cnt[N],k[N],root,top,ans,sum;
int abs(int x){return x>0?x:-x;}
void update(int x){s[x]=s[l[x]]+s[r[x]]+cnt[x];}
void l_rotate(int &x){
	int y=r[x];
	r[x]=l[y];l[y]=x;
	update(x);update(y);
	x=y;
}
void r_rotate(int &x){
	int y=l[x];
	l[x]=r[y];r[y]=x;
	update(x);update(y);
	x=y;
}
void mt(int &x,bool y){
	if (y){
		if (s[r[r[x]]]>s[l[x]]) l_rotate(x);else
		if (s[l[r[x]]]>s[r[x]])
			r_rotate(r[x]),l_rotate(x);
		else return;
	}
	else{
		if (s[l[l[x]]]>s[r[x]]) r_rotate(x);else
		if (s[r[l[x]]]>s[r[x]])
			l_rotate(l[x]),r_rotate(x);
		else return;
	}
	mt(l[x],0);mt(r[x],1);
	mt(x,1);mt(x,0);
}
void insert(int &x,int key){
	if (!x){x=++top;k[x]=key;cnt[x]=s[x]=1;return;}
	s[x]++;
	if (k[x]==key){cnt[x]++;return;}
	insert(key>k[x]?r[x]:l[x],key);
	mt(x,key>k[x]);
}
int find(int x,int R){
	if (!R) return -1e9;
	while (1){
		int i=s[l[x]];
		if (R>i&&R<=i+cnt[x]) return k[x];
		if (R>i) R-=i+cnt[x],x=r[x];
			else x=l[x];
	}
}
int rank(int x,int key){
	int ans=0;
	while (x){
		int i=s[l[x]];
		if (k[x]==key) return ans+i+1;
		if (key>k[x]) ans+=i+cnt[x],x=r[x];
			else x=l[x];
	}
	return ans;
}
void del(int &x,int key,int d){
	s[x]-=d;
	if (k[x]<key) del(r[x],key,d);
	if (k[x]>key) del(l[x],key,d);
	if (k[x]==key){
		cnt[x]-=d;
		if (cnt[x]) return;
		if (!l[x]||!r[x]){x=l[x]+r[x];return;}
		int y=r[x];
		while (l[y]) y=l[y];
		k[x]=k[y];cnt[x]=cnt[y];
		del(r[x],k[y],cnt[y]);
	}
}
void match(int b){
	int r=rank(root,b),x=find(root,r);
	int y=(r<=1?-1e9:find(root,r-1)),z=(r>=s[root]?1e9:find(root,r+1));
	if (abs(y-b)<abs(x-b)||(abs(x-b)==abs(y-b)&&y<x)) x=y;
	if (abs(z-b)<abs(x-b)||(abs(x-b)==abs(z-b)&&z<x)) x=z;
	ans=(ans+abs(x-b))%1000000;
	del(root,x,1);
}
int main()
{
	freopen("pet.in","r",stdin);
	freopen("pet.out","w",stdout);
	scanf("%d",&n);
	while (n--){
		int a,b;
		scanf("%d%d",&a,&b);
		if (!a){
			if (sum>=0) insert(root,b);
				else match(b);
			sum++;
		}
		else{
			if (sum<=0) insert(root,b);
				else match(b);
			sum--;
		}
	}
	printf("%d\n",ans);
	return 0;
}