题意：
最近，阿Q开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物，阿Q根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值a（a是一个正整数，a<2^31），而他也给每个处在收养所的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养所总是会有两种情况发生：被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少。 1． 被遗弃的宠物过多时，假若到来一个领养者，这个领养者希望领养的宠物的特点值为a，那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。（任何两只宠物的特点值都不可能是相同的，任何两个领养者的希望领养宠物的特点值也不可能是一样的）如果有两只满足要求的宠物，即存在两只宠物他们的特点值分别为a-b和a+b，那么领养者将会领养特点值为a-b的那只宠物。 2． 收养宠物的人过多，假若到来一只被收养的宠物，那么哪个领养者能够领养它呢？能够领养它的领养者，是那个希望被领养宠物的特点值最接近该宠物特点值的领养者，如果该宠物的特点值为a，存在两个领养者他们希望领养宠物的特点值分别为a-b和a+b，那么特点值为a-b的那个领养者将成功领养该宠物。 一个领养者领养了一个特点值为a的宠物，而它本身希望领养的宠物的特点值为b，那么这个领养者的不满意程度为abs(a-b)。【任务描述】你得到了一年当中，领养者和被收养宠物到来收养所的情况，希望你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时，收养所里面既没有宠物，也没有领养者。
题解：
splay裸题，记录下当前是宠物还是人，然后splay找前驱后继。
code：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
struct trnode{
int fa,son[2],c,d;
}tr[80010];int tot=0,root=0;
void update(int x)
{
int lc=tr[x].son[0],rc=tr[x].son[1];
tr[x].c=tr[lc].c+tr[rc].c+1;
}
void pushdown(int x)
{
if(x==0) return;
pushdown(tr[x].fa);update(x);
}
void add(int fa,int d)
{
tr[++tot].fa=fa;tr[tot].c=1;tr[tot].d=d;
tr[tot].son[0]=tr[tot].son[1]=0;
tr[fa].son[tr[fa].d>d?0:1]=tot;
}
void rotate(int x)
{
int y=tr[x].fa,z=tr[y].fa,w=tr[y].son[0]==x,R,r;
R=y;r=tr[x].son[w];
tr[R].son[1-w]=r;
if(r) tr[r].fa=R;
R=z;r=x;
tr[R].son[tr[z].son[1]==y]=r;
if(r) tr[r].fa=R;
R=x;r=y;
tr[R].son[w]=r;
if(r) tr[r].fa=R;
update(y);update(x);
}
void splay(int x,int fa)
{
pushdown(x);
while(tr[x].fa!=fa)
{
int y=tr[x].fa,z=tr[y].fa;
if(z==fa) rotate(x);
else
if((tr[z].son[0]==y)==(tr[y].son[0]==x)) rotate(y),rotate(x);
else rotate(x),rotate(x);
}
if(fa==0) root=x;
}
int findid(int d)
{
int x=root;
while(1)
{
update(x);
int lc=tr[x].son[0],rc=tr[x].son[1];
if(tr[x].d==d) break;
if(tr[x].d>d) {if(lc==0) break;else x=lc;}
else {if(rc==0) break;else x=rc;}
}
return x;
}
void ins(int d)
{
if(root==0) {add(0,d);root=tot;return;}
int x=findid(d);
add(x,d);
update(x);splay(x,0);
}
void del(int x)
{
splay(x,0);
int lc=tr[x].son[0],rc=tr[x].son[1];
if(lc==0&&rc==0) {tot=root=0;return;}
if(lc!=0&&rc==0) {root=lc;tr[lc].fa=0;return;}
if(lc==0&&rc!=0) {root=rc;tr[rc].fa=0;return;}
int p=lc;
while(tr[p].son[1]!=0) p=tr[p].son[1];
splay(p,x);
root=p;tr[p].fa=0;
tr[p].son[1]=rc;
tr[rc].fa=p;
update(p);
}
int findqianqu(int d)
{
int x=findid(d);
if(tr[x].d<=d) return x;
splay(x,0);
if(tr[x].son[0]==0) return -1;
x=tr[x].son[0];
while(tr[x].son[1]!=0) x=tr[x].son[1];
return x;
}
int findhouji(int d)
{
int x=findid(d);
if(tr[x].d>=d) return x;
splay(x,0);
if(tr[x].son[1]==0) return -1;
x=tr[x].son[1];
while(tr[x].son[0]!=0) x=tr[x].son[0];
return x;
}
int now=-1,ans=0,n;
bool cmin(int x,int y)
{
if(x==-1||y<x) return true;
return false;
}
void solve(int op,int d)
{
if(op==now||now==-1) {ins(d);now=op;return;}
int x1=findqianqu(d),x2=findhouji(d);
int min=-1,x;
if(x1!=-1&&cmin(min,d-tr[x1].d)) min=d-tr[x1].d,x=x1;
if(x2!=-1&&cmin(min,tr[x2].d-d)) min=tr[x2].d-d,x=x2;
ans=(ans+min)%1000000;del(x);
if(root==0) now=-1;
}
void print(int x)
{
if(x==0) return;
print(tr[x].son[0]);
printf("%d ",tr[x].d);
print(tr[x].son[1]);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int op,d;scanf("%d %d",&op,&d);
solve(op,d);
}
printf("%d",ans);
}