记录编号	408366	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 宠物收养所	最终得分	100
用户昵称	xyz117	是否通过	通过
代码语言	C++	运行时间	0.100 s
提交时间	2017-05-24 15:39:35	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
using namespace std;
const int mod=1000000;
const int inf=0x3ffffff*3;
class tree
{
    private:
        struct node
        {
            int w;
            node *fa;
            node *son[2];
            node (int v=0,node *f=NULL)
            {
                w=v;
                fa=f;
                son[0]=NULL;
                son[1]=NULL;
            }    
        }*root;
        inline bool Son(node *t,node *f)
        {
            return f->son[1]==t;    
        }
        void rotate(node *t)
        {
            node *f=t->fa;
            node *g=f->fa;
            bool a=Son(t,f),b=!a;
            f->son[a]=t->son[b];
            if(t->son[b]!=NULL)
                t->son[b]->fa=f;
            t->son[b]=f;
            f->fa=t;
            t->fa=g;
            if(g!=NULL)
                g->son[Son(f,g)]=t;
            else
                root=t;
            
        }
        void splay(node *t,node *p)
        {
            node *f,*g;
            while(t->fa!=p)
            {
                f=t->fa;
                g=f->fa;
                if(g==p)
                    rotate(t);
                else
                { 
                    if(Son(f,g)^Son(t,f))
                        rotate(t),rotate(t);
                    else    
                        rotate(f),rotate(t);
                }
            }
        }
    public:
        tree()
        {
            root=NULL;    
        }
        inline bool empty()
        {
            return root==NULL;
        }
        void insert(int w)
        {
            if(root==NULL)
                root=new node(w,NULL); 
            for(node *t=root;t;t=t->son[w>=t->w])
            {
                if(t->w==w)
                {
                    splay(t,NULL); 
                    return;
                }
                if(t->son[w>=t->w]==NULL)
                    t->son[w>=t->w]=new node(w,t);
            }  
        }
        void eraser(int w)
        {
            node *t=root;
            for(;t;)
            {
                if(t->w==w)
                    break;
                t=t->son[w>t->w];
            }    
            if(t!=NULL)
            {
                splay(t,NULL);
                if(t->son[0]==NULL)
                {
                    root=t->son[1];
                    if(root!=NULL)
                        root->fa=NULL;    
                }    
                else
                {
                    node *p=t->son[0];
                    while(p->son[1]!=NULL)
                        p=p->son[1];
                    splay(p,t);
                    root=p;
                    root->fa=NULL;
                    p->son[1]=t->son[1];
                    if(p->son[1]!=NULL)
                        p->son[1]->fa=p;    
                }
            }
        }
        int bigger(int w)
        {
            int sum=inf;
            for(node *t=root;t;)
            {
                if(t->w==w)
                    return w;
                if(t->w>w)
                    sum=min(t->w,sum);
                t=t->son[w>t->w];    
            }
            return sum;
        }
        int smaller(int w)
        {
            int sum=-inf;
            for(node *t=root;t;)
            {
                if(t->w==w)
                    return w;
                if(t->w<w)
                    sum=max(t->w,sum);
                t=t->son[w>t->w];    
            }
            return sum;
        }
    
}S;
int solve(int w)
{
    int a=S.bigger(w),b=S.smaller(w);
    if(w-b<=a-w)
    {
        S.eraser(b);
        return w-b;    
    }
    else
    {
        S.eraser(a);
        return a-w;    
    }
}
int n,wait,ans;
int main()
{
    freopen("pet.in","r",stdin);
    freopen("pet.out","w",stdout);
    int x,y;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        if(S.empty()||wait==x)
            S.insert(y),wait=x;
        else
            ans=(ans+solve(y))%mod; 
    } 
    printf("%d",ans);
    //while(1);
}