[HNOI 2004] 宠物收养所 - HeHe - 422339

记录编号	422339	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 宠物收养所	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.069 s
提交时间	2017-07-09 16:38:32	内存使用	0.82 MiB
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

namespace IO{ 
    inline char getc(void);
    inline int in(void);
    inline void write(int x);
    inline void write_all(void);

    char ops[1 << 18], *opt = ops, *const opt_end = ops + (1 << 18);

    inline char getc(void) { 
        static char buf[1 << 18], *fs, *ft;
        return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
    }

    inline int in(void) { 
        register char tmp = getc();
        register int res = 0;
        register bool f = true;

        while(!isdigit(tmp) && tmp ^ '-') tmp = getc();
        if(tmp == '-') f = false, tmp = getc();
        while(isdigit(tmp))
            res = ((res + (res << 2)) << 1) + (tmp ^ 48),
            tmp = getc();
        if(f) return res;
        return ~res + 1;
    }

    inline void write(int x) { 
        static char *p = new char[20]();
        if(x & 0x80000000) { 
            *(opt++) = '-';
            if(opt == opt_end) write_all();
            x = -x;
        }

        do{ 
            *(++p) = (x % 10) | 0x30;
            x /= 10;
        }while(x);

        while(*p) { 
            *(opt++) = *(p--);
            if(opt == opt_end) write_all();
        }

        *(opt++) = ' ';
        if(opt == opt_end) write_all();
        return ;
    }

    inline void write_all(void) { 
        fwrite(ops, 1, opt - ops, stdout);
        opt = ops;
        return ;
    }
}
using namespace IO;

const int INF = 0x6fffffff;
const int MOD = 1e6;

struct NODE{ 
    int s;
    int height, size;
    NODE *ls, *rs;

    NODE() { ;}
    NODE(int x) { 
        s = x;
        height = size = 1;
        ls = rs = NULL;
    }

    int hgt(void) { 
        if(this) return height;
        return 0;
    }

    int siz(void) { 
        if(this) return size;
        return 0;
    }

    void update(void) { 
        height = max(ls->hgt(), rs->hgt()) + 1;
        size = ls->siz() + rs->siz() + 1;
    }
};

inline int Abs(int x);
inline void Left(NODE *&k2);
inline void Right(NODE *&k2);
void Insert(NODE *&node, int x);
void Delete(NODE *&node, int x);
inline int lower_bound(NODE *node, int x);
inline int upper_bound(NODE *node, int x);

NODE *root0, *root1;
int N, arg, temp1, temp2, ANS;

int main() { 
#ifndef LOCAL
    freopen("pet.in", "r", stdin);
    freopen("pet.out", "w", stdout);
#endif
    N = in();

    for(int i = 1; i <= N; ++i) { 
        if(in()) { 
            arg = in();
            if(root0) { 
                temp1 = lower_bound(root0, arg);
                temp2 = upper_bound(root0, arg);
                if(arg - temp1 <= temp2 - arg) { 
                    Delete(root0, temp1);
                    (ANS += arg - temp1) %= MOD;
                } else { 
                    Delete(root0, temp2);
                    (ANS += temp2 - arg) %= MOD;
                }
            } else Insert(root1, arg);
        } else { 
            arg = in();
            if(root1) { 
                temp1 = lower_bound(root1, arg);
                temp2 = upper_bound(root1, arg);
                if(arg - temp1 <= temp2 - arg) { 
                    Delete(root1, temp1);
                    (ANS += arg - temp1) %= MOD;
                } else { 
                    Delete(root1, temp2);
                    (ANS += temp2 - arg) %= MOD;
                }
            } else Insert(root0, arg);
        }
    }

    printf("%d", ANS);
    return 0;
}

inline void Left(NODE *&k2) { 
    register NODE *k1 = k2->ls;
    k2->ls = k1->rs;
    k1->rs = k2;

    k2->update(); k1->update();
    k2 = k1;
    return ;
}

inline void Right(NODE *&k2) { 
    register NODE *k1 = k2->rs;
    k2->rs = k1->ls;
    k1->ls = k2;

    k2->update(); k1->update();
    k2 = k1;
    return ;
}

inline int Abs(int x) { 
    if(x & 0x80000000) return ~x + 1;
    return x;
}

void Insert(NODE *&node, int x) { 
    if(node) { 
        if(x < node->s) { 
            Insert(node->ls, x);
            if(node->ls->hgt() - node->rs->hgt() == 2) { 
                if(node->ls->rs->hgt() > node->ls->ls->hgt()) Right(node->ls);
                Left(node);
            } else node->update();
        } else { 
            Insert(node->rs, x);
            if(node->rs->hgt() - node->ls->hgt() == 2) { 
                if(node->rs->ls->hgt() > node->rs->rs->hgt()) Left(node->rs);
                Right(node);
            } else node->update();
        }
    } else node = new NODE(x);
    return ;
}

void Delete(NODE *&node, int x) { 
    if(x ^ node->s) { 
        if(x < node->s) { 
            Delete(node->ls, x);
            if(node->rs->hgt() - node->ls->hgt() == 2) { 
                if(node->rs->ls->hgt() > node->rs->rs->hgt()) Left(node->rs);
                Right(node);
            } else node->update();
        } else { 
            Delete(node->rs, x);
            if(node->ls->hgt() - node->rs->hgt() == 2) { 
                if(node->ls->rs->hgt() > node->ls->ls->hgt()) Right(node->ls);
                Left(node);
            } else node->update();
        }
    } else { 
        if(node->ls && node->rs) { 
            register NODE *temp = node->rs;
            while(temp->ls) temp = temp->ls;
            node->s = temp->s;
            Delete(node->rs, node->s);
            
            if(node->ls->hgt() - node->rs->hgt() == 2) { 
                if(node->ls->rs->hgt() > node->ls->ls->hgt()) Right(node->ls);
                Left(node);
            } else node->update();
        } else { 
            register NODE *temp = node;
            if(node->ls) node = node->ls;
            else node = node->rs;
            delete temp;
        }
    }
    return ;
}

inline int lower_bound(NODE *node, int x) { 
    register int res = -INF;

    while(node) { 
        if(x == node->s) return x;
        else if(x < node->s) node = node->ls;
        else { 
            res = node->s;
            node = node->rs;
        }
    }

    return res;
}

inline int upper_bound(NODE *node, int x) { 
    register int res = INF;

    while(node) { 
        if(x == node->s) return x;
        else if(x > node->s) node = node->rs;
        else { 
            res = node->s;
            node = node->ls;
        }
    }

    return res;
}