Description

最近, 阿 Q 开了一间宠物收养所. 收养所提供两种服务: 收养被主人遗弃的宠物和让新的主人 领养这些宠物. 每个领养者都希望领养到自己满意的宠物, 阿 Q 根据领养者的要求通过他自己发明的一个特殊的公式, 得出该领养者希望领养的宠物的特点值 \(a\) (\(a\) 是一个正整数,\(a \lt 2^{31}\)) , 而他也给每个处在收养所的宠物一个特点值. 这样他就能够很方便的 处理整个领养宠物的过程了, 宠物收养所总是会有两种情况发生: 被遗弃的宠物过多或者是想要收养宠物的人太多, 而宠物太少.

  1. 被遗弃的宠物过多时, 假若到来一个领养者, 这个领养者希望领养的宠物的特点值为 \(a\), 那么它将会领养一只目前未被领养的宠物中特点值最接近 \(a\) 的一只宠物. (任何两只宠物的特点值都不可能是相同的, 任何两个领养者的希望领养宠物的特点值 也不可能是一样的) 如果有两只满足要求的宠物, 即存在两只宠物他们的特点值分别为 \(a - b\) 和 \(a + b\), 那么领养者将会领养特点值为 \(a - b\) 的那只宠物.
  2. 收养宠物的人过多, 假若到来一只被收养的宠物, 那么哪个领养者能够领养它呢? 能够 领养它的领养者, 是那个希望被领养宠物的特点值最接近该宠物特点值的领养者, 如果 该宠物的特点值为 \(a\), 存在两个领养者他们希望领养宠物的特点值分别为 \(a - b\) 和 \(a + b\), 那么特点值为 \(a - b\) 的那个领养者将成功领养该宠物.

一个领养者领养了一个特点值为 \(a\) 的宠物, 而它本身希望领养的宠物的特点值为 \(b\), 那么这个领养者的不满意程度为 \(|a - b|\).

你得到了一年当中, 领养者和被收养宠物到来收养所的情况, 希望你计算所有收养了宠物的领养者的不满意程度的总和. 这一年初始时, 收养所里面既没有宠物, 也没有领养者.

Input

第一行为一个正整数 \(n, n \leq 80000\), 表示一年当中来到收养所的宠物和领养者的总数. 接下来的 \(n\) 行, 按到来时间的先后顺序描述了一年当中来到收养所的宠物和领养者的 情况. 每行有两个正整数 \(a, b\), 其中 \(a = 0\) 表示宠物,\(a = 1\) 表示领养者,\(b\) 表示宠物的特点值或是领养者希望领养宠物的特点值. (同一时间呆在收养所中的, 要么 全是宠物, 要么全是领养者, 这些宠物和领养者的个数不会超过 \(10000\) 个)

Output

仅有一个正整数, 表示一年当中所有收养了宠物的领养者的不满意程度的总和 \(\bmod 1000000\) 以后的结果.

Sample Input

5
0 2
0 4
1 3
1 2
1 5

Sample Output

3

Explanation

研究发现宠物和领养者是轮换对称的, 换句话说就是他们是等价的...... 那么我们还是可以 直接用 STL 中的各种二分搜索函数来瞎搞 (如果你想自己写一个 Splay 锻炼锻炼代码水平 我可不会拦你, 写挂了后果自负, 与作者本人无关), 只需要在 set 的值上打一个标记 即可.

后来想想, 一个时间只会出现一种实体对不对, 所以只需要打一个全局 flag 就可以了.

然后此题水过~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <set>

using namespace std;
typedef long long lli;
const lli infinit = 0x007f7f7f7f7f7f7fll;
const lli modr = 1000000;

int n, type;
set<lli> st;
lli res = 0;

void query(lli v)
{
    set<lli>::iterator
        li = --st.lower_bound(v),
        ri = st.upper_bound(v);
    lli l = *li, r = *ri;
    if (v - l <= r - v && l != -infinit) {
        // Better to choose the smaller one
        res = (res + v-l) % modr;
        st.erase(l);
    } else {
        // Then we shall choose the larger one
        res = (res + r-v) % modr;
        st.erase(r);
    }
    return ;
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    // Setting limitations, in case we need to check the cases...
    st.insert(-infinit);
    st.insert(infinit);
    for (lli i = 1, x, y; i <= n; i++) {
        scanf("%lld%lld", &x, &y);
        // It is guranteed that there will be only one type of entity in
        // the area.
        if (st.size() <= 2) {
            type = x;
            st.insert(y);
        } else if (x == type) {
            st.insert(y);
        } else {
            query(y);
        }
    }
    // Output result
    printf("%lld\n", res);
    return 0;
}