记录编号 |
424156 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[HNOI 2004] 宠物收养所 |
最终得分 |
100 |
用户昵称 |
Hzoi_Mafia |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.053 s |
提交时间 |
2017-07-12 21:11:45 |
内存使用 |
0.27 MiB |
显示代码纯文本
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
inline int read(){
int sum(0);
char ch(getchar());
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9'){
sum=sum*10+ch-'0';
ch=getchar();
}
return sum;
}
int n;
struct node{
node *ch[2];
int v,k,size;
node(int x=0):v(x),k(rand()),size(1){
ch[0]=ch[1]=NULL;
}
}*root;
inline int get_size(node *x){
if(x==NULL)
return 0;
return x->size;
}
inline void pushup(node *x){
x->size=get_size(x->ch[0])+get_size(x->ch[1])+1;
}
inline void ro(node *&rt,int d){
node *tmp(rt->ch[d^1]);
rt->ch[d^1]=tmp->ch[d];
pushup(rt);
tmp->ch[d]=rt;
pushup(tmp);
rt=tmp;
}
inline void insert(node *&rt,int x){
if(rt==NULL){
rt=new node(x);
return;
}
int d(rt->v>x);
insert(rt->ch[d^1],x);
pushup(rt);
if(rt->ch[d^1]->k>rt->k)
ro(rt,d);
}
inline void del(node *&rt,int x){
if(rt->v==x){
if(rt->ch[0]!=NULL&&rt->ch[1]!=NULL){
int d(rt->ch[0]->k>rt->ch[1]->k);
ro(rt,d);
del(rt->ch[d],x);
}
else{
node *tmp(NULL);
if(rt->ch[0]!=NULL)
tmp=rt->ch[0];
else
tmp=rt->ch[1];
delete rt;
rt=tmp;
}
}
else{
int d(rt->v>x);
del(rt->ch[d^1],x);
}
if(rt!=NULL)
pushup(rt);
}
inline int rk(int x){
node *rt(root);
int ret(0);
while(rt){
if(x>rt->v){
ret+=get_size(rt->ch[0])+1;
rt=rt->ch[1];
}
else
rt=rt->ch[0];
}
return ret;
}
inline int kth(int k){
node *rt(root);
while(rt){
if(get_size(rt->ch[0])+1==k)
return rt->v;
if(get_size(rt->ch[0])+1>k)
rt=rt->ch[0];
else{
k-=get_size(rt->ch[0])+1;
rt=rt->ch[1];
}
}
return 0;
}
inline bool find(node *rt,int x){
node *now(root);
while(now){
if(now->v==x)
return true;
if(now->v>x)
now=now->ch[0];
else
now=now->ch[1];
}
return false;
}
int s[2]={0};
int ans(0);
inline int jdz(int x){
return x>=0?x:-x;
}
inline void query(int x){
int fn(kth(rk(x)));
int fx(kth(rk(x+1)+1));
if(fn==0){
ans+=jdz(fx-x);
del(root,fx);
ans%=1000000;
return;
}
if(fx==0){
ans+=jdz(fn-x);
del(root,fn);
ans%=1000000;
return;
}
int jn=jdz(fn-x),jx=jdz(fx-x);
if(jn==jx){
ans+=jn;
ans%=1000000;
del(root,fn);
return;
}
if(jn>jx){
del(root,fx);
ans+=jx;
}
else{
del(root,fn);
ans+=jn;
}
ans%=1000000;
}
inline int ain(){
freopen("pet.in","r",stdin);
freopen("pet.out","w",stdout);
srand(time(NULL));
n=read();
for(int i=1;i<=n;i++){
int op(read()),x(read());
if(s[op^1]){
if(find(root,x))
continue;
query(x);
s[op^1]--;
}
else{
s[op]++;
insert(root,x);
}
}
printf("%d",ans);
}
int in(ain());
int main(){;}