记录编号	22942	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 宠物收养所	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.125 s
提交时间	2011-01-24 13:51:24	内存使用	0.32 MiB

#include <iostream>
#include <fstream>
#include <set>

using namespace std;

int main(void)
{
	ifstream fin("pet.in");
	ofstream fout("pet.out");
	int n,a,b,mode=0,ans=0;
	set<int> rec;
	set<int>::iterator ita,itb;

	fin>>n;
	for (int i=0; i<n; i++)
	{
		fin>>a>>b;
		if (a==mode)
			rec.insert(b);
		else if (rec.size()>0)
		{
			ita=rec.lower_bound(b);
			if (ita==rec.begin()) ita=rec.end(); else ita--;
			itb=rec.lower_bound(b);

			if (itb!=rec.end() && (ita==rec.end() || b-*ita > *itb-b))
			{
				ans+=*itb-b;
				rec.erase(itb);
			}
			else if (ita!=rec.end() && (itb==rec.end() || b-*ita < *itb-b))
			{
				ans+=b-*ita;
				rec.erase(ita);
			}
			else if (a && itb!=rec.end())
			{
				ans+=b-*ita;
				rec.erase(ita);
			}
			else if (ita!=rec.end())
			{
				ans+=*itb-b;
				rec.erase(itb);
			}
		}
		else
		{
			mode=a;
			rec.insert(b);
		}

		ans%=1000000;
	}

	fout<<ans<<endl;

	return 0;
}