记录编号	432798	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 宠物收养所	最终得分	100
用户昵称	Hzoi_QTY	是否通过	通过
代码语言	C++	运行时间	0.030 s
提交时间	2017-08-03 20:11:10	内存使用	0.26 MiB

#include<cstdio>  
#include<cstring>  
#include<set>
#include<iostream>
#include<cmath>
#define inf 1000000000
using namespace std;
set<int> st;
int n,m,ans,mod=1000000;
inline int read()
{
	int sum=0,f=1;char x=getchar();
	while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
	while(x>='0'&&x<='9'){sum=sum*10+x-'0';x=getchar();}
	return sum*f;
}
int yjn()
{
	freopen("pet.in","r",stdin);
    freopen("pet.out","w",stdout);
	n=read();
	int x,y;
	for(int i=1;i<=n;i++)
	{   
		x=read();y=read();
		
		if(st.empty())
		{st.insert(y);
			m=x;continue;
		}
		if(m!=x)
		{
			int a=inf,b=inf;
			set<int>::iterator it=st.lower_bound(y);
			set<int>::iterator it2=it;
			if(it!=st.begin())it--;
			if(it2==st.end())it2--;
			a=abs(y-*it);b=abs(*it2-y);
			if(a<=b){ans=(ans+a)%mod;st.erase(*it);}
			else    {ans=(ans+b)%mod;st.erase(*it2);}
		}
		else
		    st.insert(y);
	}
	printf("%d\n",ans);
}
int qty=yjn();
int main(){;}