记录编号	34982	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 宠物收养所	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.287 s
提交时间	2012-02-13 19:31:30	内存使用	0.26 MiB

#include <cstdio>
#include <cstdlib>
#include <set>
using namespace std;
typedef set<int>  Set;

const int MOD=1000000;
int N;
Set Pet,Owner;

int abs(int x)
{return x>0?x:-x;}

int Maintenance(Set& A,Set& B,int m)
{
	int res=0;
	if(A.size()==0)
	{
		B.insert(m);
		return 0;
	}
	Set::iterator iter;
	iter=A.lower_bound(m);
	if(iter==A.end())
	{
		iter--;
		res=abs(*iter-m);
		A.erase(iter);
		return res;
	}
	if(*iter==m)
	{
		A.erase(iter);
		return 0;
	}
	if(iter==A.begin())
	{
		res=abs(*iter-m);
		A.erase(iter);
		return res;
	}
	Set::iterator tmp;
	res=abs(*iter-m);
	tmp=iter;
	
	iter--;
	if(abs(*iter-m)<=res)
	{
		res=abs(*iter-m);
		tmp=iter;
	}
	A.erase(tmp);
	return res;
}

void init()
{
	int Ans=0;
	scanf("%d\n",&N);
	int x,m;
	for(int i=1;i<=N;i++)
	{
		scanf("%d %d\n",&x,&m);
		if(!x)
			Ans+=Maintenance(Owner,Pet,m);
		else
			Ans+=Maintenance(Pet,Owner,m);
		Ans%=MOD;
	}	
	printf("%d\n",Ans);
}
 
int main()
{
	freopen("pet.in","r",stdin);
	freopen("pet.out","w",stdout);
	init();
	return 0;
}