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

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <set>
using namespace std;
set<int>q;
int main(){
	freopen("pet.in","r",stdin);
	freopen("pet.out","w",stdout);
	int n,a,p,ans=0,flag=-1;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&p,&a);
		if(flag==-1){
			q.insert(a);
			flag=p;
		}
		else if(flag==p)
			q.insert(a);

		else{
			set<int>::iterator l,r,tmp;
			r=q.upper_bound(a);
			if(r==q.end()){
				r--;
				ans=(ans+a-*r)%1000000;
				q.erase(r);
			}
			else if(r==q.begin()){
				ans=(ans+*r-a)%1000000;
				q.erase(r);
			}
			else{
				tmp=r;l=--tmp;
				if(*r-a<a-*l){
					ans=(ans+*r-a)%1000000;
					q.erase(r);
				}
				else{
					ans=(ans+a-*l)%1000000;
					q.erase(l);
				}
			}
			if(q.size()==0)
				flag=-1;
		}
			
	}
	printf("%d\n",ans%1000000);
}