一道比较简单的直接Treap运用题目，思维难度和代码难度都不是很高。
题意有点长，我们仔细剖析一下题意发现以下几个关键：
- 任何时候收养站里只可能有人和宠物中的其中一种，或者都没有
- 如果只有宠物并有人来时，那个人会立刻挑选一只宠物并离开（只有人的时候同理）。
- 如果没有宠物并有人来时，那个人会一直等着直到有宠物到来并且那个宠物被它领养了（没有人的时候同理）。
然后我们思考一下那个选宠物（或者是宠物选人）的过程，其实就是在一个集合找一个数和它最接近的过程。
然后这道题已经很良心地提示你了：
存在两个宠物a-b，a+b......
其实仔细想一下就是一个找前驱和找后缀的问题，我们找出前驱和后继就可以直接统计并删除了。
具体实现的时候开两个Treap，一棵存宠物，一棵存人（这里由于宠物和人只会同时存在一种，所以其实开一棵也可以），然后按题意搞一下就可以了。
然后我写了两个namespace，所以主程序看上去有点乱。
最后注意开long long
CODE
#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const LL N=80005,INF=1e18,mod=1000000;
LL n,opt,x,ans;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(LL &x)
{
x=0; char ch; while (!isdigit(ch=tc()));
while (x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));
}
inline LL rand(void)
{
static LL seed=233;
return seed=(LL)seed*482711LL%2147483647;
}
inline LL min(LL a,LL b)
{
return a<b?a:b;
}
namespace pet
{
struct Treap
{
LL ch[2],val,dat;
}node[N];
LL tot,rt,size;
inline LL build(LL v)
{
node[++tot].val=v; node[tot].dat=rand(); return tot;
}
inline void init(void)
{
rt=build(-INF); node[rt].ch[1]=build(INF);
}
inline void rotate(LL &rt,LL d)
{
LL temp=node[rt].ch[d^1]; node[rt].ch[d^1]=node[temp].ch[d];
node[temp].ch[d]=rt; rt=temp;
}
inline void insert(LL &rt,LL v)
{
if (!rt) { rt=build(v); return; }
LL d=v<node[rt].val?0:1; insert(node[rt].ch[d],v);
if (node[rt].dat<node[node[rt].ch[d]].dat) rotate(rt,d^1);
}
inline void remove(LL &rt,LL v)
{
if (node[rt].val==v)
{
if (node[rt].ch[0]||node[rt].ch[1])
{
if (!node[rt].ch[1]||node[node[rt].ch[1]].dat<node[node[rt].ch[0]].dat) rotate(rt,1),remove(node[rt].ch[1],v);
else rotate(rt,0),remove(node[rt].ch[0],v);
} else rt=0; return;
}
if (v<node[rt].val) remove(node[rt].ch[0],v); else remove(node[rt].ch[1],v);
}
inline LL get_pre(LL rt,LL v)
{
LL pre;
while (rt)
{
if (node[rt].val<=v) pre=node[rt].val,rt=node[rt].ch[1];
else rt=node[rt].ch[0];
}
return pre;
}
inline LL get_next(LL rt,LL v)
{
LL next;
while (rt)
{
if (node[rt].val>=v) next=node[rt].val,rt=node[rt].ch[0];
else rt=node[rt].ch[1];
}
return next;
}
};
namespace hum
{
struct Treap
{
LL ch[2],val,dat;
}node[N];
LL tot,rt,size;
inline LL build(LL v)
{
node[++tot].val=v; node[tot].dat=rand(); return tot;
}
inline void init(void)
{
rt=build(-INF); node[rt].ch[1]=build(INF);
}
inline void rotate(LL &rt,LL d)
{
LL temp=node[rt].ch[d^1]; node[rt].ch[d^1]=node[temp].ch[d];
node[temp].ch[d]=rt; rt=temp;
}
inline void insert(LL &rt,LL v)
{
if (!rt) { rt=build(v); return; }
LL d=v<node[rt].val?0:1; insert(node[rt].ch[d],v);
if (node[rt].dat<node[node[rt].ch[d]].dat) rotate(rt,d^1);
}
inline void remove(LL &rt,LL v)
{
if (node[rt].val==v)
{
if (node[rt].ch[0]||node[rt].ch[1])
{
if (!node[rt].ch[1]||node[node[rt].ch[1]].dat<node[node[rt].ch[0]].dat) rotate(rt,1),remove(node[rt].ch[1],v);
else rotate(rt,0),remove(node[rt].ch[0],v);
} else rt=0; return;
}
if (v<node[rt].val) remove(node[rt].ch[0],v); else remove(node[rt].ch[1],v);
}
inline LL get_pre(LL rt,LL v)
{
LL pre;
while (rt)
{
if (node[rt].val<=v) pre=node[rt].val,rt=node[rt].ch[1];
else rt=node[rt].ch[0];
}
return pre;
}
inline LL get_next(LL rt,LL v)
{
LL next;
while (rt)
{
if (node[rt].val>=v) next=node[rt].val,rt=node[rt].ch[0];
else rt=node[rt].ch[1];
}
return next;
}
};
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
pet::init(); hum::init(); read(n);
while (n--)
{
read(opt); read(x);
if (opt)
{
if (pet::size)
{
LL pre=pet::get_pre(pet::rt,x),next=pet::get_next(pet::rt,x); --pet::size;
if (pre==-INF||x-pre>next-x) ans=(ans+next-x)%mod,pet::remove(pet::rt,next);
else ans=(ans+x-pre)%mod,pet::remove(pet::rt,pre);
} else ++hum::size,hum::insert(hum::rt,x);
} else
{
if (hum::size)
{
LL pre=hum::get_pre(hum::rt,x),next=hum::get_next(hum::rt,x); --hum::size;
if (pre==-INF||x-pre>next-x) ans=(ans+next-x)%mod,hum::remove(hum::rt,next);
else ans=(ans+x-pre)%mod,hum::remove(hum::rt,pre);
} else ++pet::size,pet::insert(pet::rt,x);
}
}
return printf("%lld",ans),0;
}