记录编号	11115	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 宠物收养所	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	0.518 s
提交时间	2009-07-15 10:05:19	内存使用	1.48 MiB

/* 
 * Problem: 宠物收养所
 * Author: Guo Jiabao
 * Time: 2009.7.15 9:26
 * State: Unsolved
 * Memo: Treap
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=80001,MOD=1000000,INF=~0U>>1;
struct Treap
{
	struct Treap_Node
	{
		Treap_Node *c[2];
		int value,fix;
	}*root,TS[MAXN];
	int TC;
	Treap_Node * NewNode(int value)
	{
		Treap_Node *p = TS + (++TC);
		p -> value = value;
		p -> c[0] = p -> c[1] = 0;
		p -> fix = rand();
		return p;
	}
	void Rotate(Treap_Node *&p,int o)
	{
		Treap_Node *q = p->c[o];
		p->c[o] = q->c[!o];
		q->c[!o] = p;
		p = q;
	}
	void Insert(Treap_Node *&p,int value)
	{
		if (!p)
			p = NewNode(value);
		else if (value <= p->value)
		{
			Insert(p->c[0],value);
			if (p->c[0]->fix < p->fix)
				Rotate(p,0);
		}
		else
		{
			Insert(p->c[1],value);
			if (p->c[1]->fix < p->fix)
				Rotate(p,1);
		}
	}
	void Delete(Treap_Node *&p,int value)
	{
		if (p->value == value)
		{
			if (p->c[0] && p->c[1])
			{
				if (p->c[0]->fix < p->c[1]->fix)
				{
					Rotate(p,0);
					Delete(p->c[1],value);
				}
				else
				{
					Rotate(p,1);
					Delete(p->c[0],value);
				}
			}
			else
			{
				if (p->c[0])
					p = p->c[0];
				else
					p = p->c[1];
			}
		}
		else if (value < p->value)
			Delete(p->c[0],value);
		else
			Delete(p->c[1],value);
	}
	inline int max(int a,int b) {return a>b?a:b;}
	inline int min(int a,int b) {return a<b?a:b;}
	int prev(Treap_Node *p,int value)
	{
		if (!p) return -INF;
		if (p->value <= value)
			return max(p->value,prev(p->c[1],value));
		else
			return prev(p->c[0],value);
	}
	int succ(Treap_Node *p,int value)
	{
		if (!p) return INF;
		if (p->value >= value)
			return min(p->value,succ(p->c[0],value));
		else
			return succ(p->c[1],value);
	}
}T;
int N,Ans;
void init()
{
	freopen("pet.in","r",stdin);
	freopen("pet.out","w",stdout);
	scanf("%d",&N);
	Ans = 0;
	T.root = 0;
}
void solve()
{
	int i,a,p,prev,succ;
	bool pet;
	for (i=1;i<=N;i++)
	{
		scanf("%d%d",&a,&p);
		if (!T.root)
			pet = a == 0;
		if (!(pet ^ (a==0)))
			T.Insert(T.root,p);
		else
		{
			prev = T.prev(T.root,p);
			succ = T.succ(T.root,p);
			if ((succ == INF) || (prev != -INF && p - prev <= succ - p))
			{
				T.Delete(T.root,prev);
				Ans += p - prev;
			}
			else
			{
				T.Delete(T.root,succ);
				Ans += succ - p;
			}
			Ans %= MOD;
		}
	}
}
int main()
{
	init();
	solve();
	printf("%d\n",Ans);
	return 0;
}