平衡树的题。
因为题目给出条件（其实自己也知道）：同一时间呆在收养所中的，要么全是宠物，要么全是领养者，这些宠物和领养者的个数不会超过10000个。
所以只要维护一颗平衡树，它的里面要不全是人，要不全是宠物。
找到人的前驱后继比较。
code：
/**************************************************************
Problem: 1208
User: yekehe
Language: C++
Result: Accepted
Time:180 ms
Memory:2388 kb
****************************************************************/ #include <cstdio>
#include <cstdlib>
using namespace std; int read()
{
char c;while(c=getchar(),c<''||c>'');
int x=c-'';while(c=getchar(),c>=''&&c<='')x=x*+c-'';
return x;
} int N,now,root,cnt,dist;
int tr[][],v[],r[],f[]; void clear(int x){f[x]=tr[x][]=tr[x][]=r[x]=v[x]=;}
void up(int x){f[x]=f[tr[x][]]+f[tr[x][]];}
int abs(int x){return x>?x:-x;} void rotate(int &x,int o)
{
int k=tr[x][o];
tr[x][o]=tr[k][o^];
tr[k][o^]=x;
f[k]=f[x];
up(x);
x=k;
} void insert(int &x,int val)
{
if(!x){
x=++cnt;
v[x]=val;
r[x]=rand();
f[x]++;
return ;
}
int to=val>v[x];
insert(tr[x][to],val);
if(r[x]>r[tr[x][to]])rotate(x,to);
return ;
} void del(int &x,int val)
{
if(v[x]==val){
if(!(tr[x][]+tr[x][])){
clear(x);x=;
return ;
}
if(!(tr[x][]*tr[x][])){
int w=tr[x][]+tr[x][];
clear(x);x=w;
return ;
}
rotate(x,);
del(x,val);
return ;
}
f[x]--;
int to=val>v[x];
del(tr[x][to],val);
up(x);
return ;
} void pre(int x,int val)//前驱
{
if(!x)return ;
if(v[x]>=val)pre(tr[x][],val);
else{
dist=x;
pre(tr[x][],val);
}
} void bac(int x,int val)//后继
{
if(!x)return ;
if(v[x]<=val)bac(tr[x][],val);
else{
dist=x;
bac(tr[x][],val);
}
} int main()
{
srand();
N=read();
int i,ans=,o1,o2,tot=;
for(i=;i<=N;i++){
int x=read(),y=read();
if(!tot){insert(root,y),now=x;tot++;continue;}
if(now==x)insert(root,y),tot++;
else{
dist=;pre(root,y);o1=dist;
dist=;bac(root,y);o2=dist;
if(!o1&&!o2)continue;
int k1=o1?y-v[o1]:2e9,k2=o2?v[o2]-y:2e9;
dist=k1>k2?o2:o1;//找较接近的值
ans=(ans+abs(v[dist]-y))%;
del(root,v[dist]);
tot--;
}
}
printf("%d",ans);
return ;
}