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

#include <cstdio>
#include <set>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
set<int> pet, host;
int cnt;
#define MOD 1000000
void add(set<int> &a, set<int> &b, int v)
{
    if(!b.size())
    {
        a.insert(v);
        return;
    }
    set<int>::iterator pc, pl;
    pc = b.lower_bound(v);
    int ans;
    if(pc == b.end() || pc == b.begin())
    {
        if(pc == b.end())pc--;
        ans = abs(*pc-v);
        b.erase(pc);
        cnt = (cnt+ans)%MOD;
        return;
    }
    ans = abs(*pc-v);
    pl = pc;
    pl--;
    int tmp = abs(*pl-v);
    if(tmp <= ans)
    {
        pc = pl;
        ans = tmp;
    }
    b.erase(pc);
    cnt = (cnt+ans)%MOD;
}
int main()
{
    freopen("pet.in","r",stdin);
	freopen("pet.out","w",stdout);
    int n;scanf("%d", &n);
    while(n--)
    {
        int x, y;scanf("%d %d", &x, &y);
        if(!x)add(pet, host, y);
        else add(host, pet, y);
    }
    printf("%d\n", cnt);
    return 0;
}