记录编号	263212	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 宠物收养所	最终得分	100
用户昵称	lingyixiaoyao	是否通过	通过
代码语言	C++	运行时间	0.127 s
提交时间	2016-05-23 22:31:57	内存使用	0.31 MiB

#include <cstdio>
#include <iostream>
#include <cstring>
#include <climits>
#include <string>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
 
int n,p,q;
multiset <int> aa;
multiset <int> ren;
int min1;
 
int main()
{
	freopen("pet.in","r",stdin);
	freopen("pet.out","w",stdout);
	aa.insert(INT_MAX/2);
	aa.insert(INT_MIN/2);
	ren.insert(INT_MAX/2);
	ren.insert(INT_MIN/2); 
	
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&p,&q);
		if(p==0)
		{
			if(ren.size()==2)
			{
				aa.insert(q);
			}
			else
			{
				int a,b;
				a=*ren.lower_bound(q);
				b=*(--ren.lower_bound(q));
				if(abs(a-q)>=abs(b-q))
				{
					ren.erase(--ren.lower_bound(q));
					min1=(min1+abs(b-q))%1000000;
				}
				else
				{
					ren.erase(ren.lower_bound(q));
					min1=(min1+abs(a-q))%1000000;
				}
			}
		}
		else
		{
			if(aa.size()==2)
			{
				ren.insert(q);
			}
			else
			{
				int a,b;
				a=*aa.lower_bound(q);
				b=*(--aa.lower_bound(q));
				if(abs(a-q)>=abs(b-q))
				{
					aa.erase(--aa.lower_bound(q));
					min1=(min1+abs(b-q))%1000000;
				}
				else
				{
					aa.erase(aa.lower_bound(q));
					min1=(min1+abs(a-q))%1000000;
				}
			}
		}
	}
	cout<<min1<<endl;
	return 0;
}