记录编号	36902	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 宠物收养所	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	0.260 s
提交时间	2012-03-21 09:23:16	内存使用	0.27 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>

using namespace std;

const int oo=~0u>>2;
const int MOD=1000000;

struct Node
{
	int key,size;
	Node *c[2];
	Node():key(0),size(0){c[0]=c[1]=this;}
	Node *rz(){return size=c[0]->size+c[1]->size+1,this;}
	Node(int _key,Node *c0,Node *c1):key(_key){c[0]=c0;c[1]=c1;}
};

struct Splaytree
{
	Node *root,*null;
	Splaytree()
	{
		null=new Node();
		root=new Node(-oo,null,null);
		root->c[1]=new Node(oo,null,null);
		root->c[1]->rz();
		root->rz();
	}
	void zig(bool d)
	{
		Node *p=root->c[d];
		root->c[d]=null->c[d];
		null->c[d]=root;
		root=p;
	}
	void zigzig(bool d)
	{
		Node *p=root->c[d]->c[d];
		root->c[d]->c[d]=null->c[d];
		null->c[d]=root->c[d];
		root->c[d]=root->c[d]->c[!d];
		null->c[d]->c[!d]=root->rz();
		root=p;
	}
	void finish(bool d)
	{
		Node *p=root->c[!d],*t=null->c[d];
		while(t!=null)
		{
			t=null->c[d]->c[d];
			null->c[d]->c[d]=p;
			p=null->c[d]->rz();
			null->c[d]=t;
		}
		root->c[!d]=p;
	}
	void select(int k)
	{
		int t;
		for(;;)
		{
			bool d=k>(t=root->c[0]->size);
			if(k==t||root->c[d]==null)
				break;
			if(d)
				k-=t+1;
			bool dd=k>(t=root->c[d]->c[0]->size);
			if(k==t||root->c[d]->c[dd]==null)
			{
				zig(d);
				break;
			}
			if(dd)
				k-=t+1;
			d!=dd?zig(d),zig(dd):zigzig(d);
		}
		finish(0);
		finish(1);
		root->rz();
	}
	void search(int x)
	{
		for(;;)
		{
			bool d=x>root->key;
			if(root->c[d]==null)
				break;
			bool dd=x>root->c[d]->key;
			if(root->c[d]->c[dd]==null)
			{
				zig(d);
				break;
			}
			d!=dd?zig(d),zig(dd):zigzig(d);
		}
		finish(0);
		finish(1);
		root->rz();
		if(root->key<x)
			select(root->c[0]->size+1);
	}
	bool empty()
	{
		return (root->size==2);
	}
	void insert(int x)
	{
		search(x);
		root=new Node(x,root->c[0],root);
		root->c[1]->c[0]=null;
		root->c[1]->rz();
		root->rz();
	}
	int get(int x)
	{
		search(x);
		int re=abs(x-root->key);
		select(root->c[0]->size-1);
		if (abs(x-root->key)<=re)
			re=abs(x-root->key);
		else
			select(root->c[0]->size+1);
		Node *oldroot=root;
		root=root->c[1];
		select(0);
		root->c[0]=oldroot->c[0];
		root->rz();
		return re;
	}
}splay;

int N,ans;

int main()
{
	freopen("pet.in","r",stdin);
	freopen("pet.out","w",stdout);
	scanf("%d",&N);
	int c=-1;
	for(int i=1;i<=N;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		if(c==-1)
			c=a;
		if(c==a)
			splay.insert(b);
		else
		{
			ans=(ans+splay.get(b))%MOD;
			if(splay.empty())
				c=-1;
		}
	}
	printf("%d\n",ans);
	return 0;
}