点个赞

#include <bits/stdc++.h>
#define LL long long

#define ULL unsigned long long

#define LD long double

#define int long long


using namespace std;

const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const LL INFll = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e6;

#define lc(x) ch[x][0]

#define rc(x) ch[x][1]


int psz;
int a[N];
int key[N], pri[N], siz[N], ch[N][2];

int node(int k) {
    int u = ++psz;
    key[u] = k, pri[u] = rand(), siz[u] = 1, lc(u) = rc(u) = 0;
    return u;
}

void maintain(int u) {
    siz[u] = siz[lc(u)] + siz[rc(u)] + 1;
}

void split(int u, int k, int &l, int &r) {
    if(!u) {
        l = r = 0;
        return;
    }
    if (k <= key[u]) {
        split(lc(u), k, l, lc(u)), r = u;
    } else {
        split(rc(u), k, rc(u), r), l = u;
    }
    maintain(u);
}

int merge(int u, int v) {
    if (u == 0 || v == 0) {
        return u ^ v;
    }
    if (pri[u] < pri[v]) {
        rc(u) = merge(rc(u), v);
        maintain(u);
        return u;
    } else {
        lc(v) = merge(u, lc(v));
        maintain(v);
        return v;
    }
}

void insert(int &root, int k) {
    int l, r;
    split(root, k, l, r);
    root = merge(merge(l, node(k)), r);
}

void erase(int &root, int k) {
    int l, u, r;
    split(root, k, l, u);
    split(u, k + 1, u, r);
    u = merge(lc(u), rc(u));
    root = merge(merge(l, u), r);
}

int Rank(int root, int k) {
    int ret = 0, u = root;
    while (u) {
        if (k <= key[u]) {
            u = lc(u);
        } else {
            ret += siz[lc(u)] + 1;
            u = rc(u);
        }
    }
    return ret + 1;
}

int Select(int root, int k) {
    int u = root;
    while (u) {
        if (siz[lc(u)] + 1 == k) {
            break;
        } else if (k <= siz[lc(u)]) {
            u = lc(u);
        } else {
            k -= (siz[lc(u)] + 1), u = rc(u);
        }
    }
    return key[u];
}

int Prev(int root, int k) {
    return Select(root, Rank(root, k) - 1);
}

int Next(int root, int k) {
    return Select(root, Rank(root, k + 1));
}

void dfs(int u) {
    if (!u) {
        return;
    }
    dfs(lc(u));
    cout << key[u] << " ";
    dfs(rc(u));
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int r0 = 0, r1 = 0;
    insert(r0, -INF);
    insert(r0, INF);
    insert(r1, -INF);
    insert(r1, INF);
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        int opt, x;
        cin >> opt >> x;
        if (opt == 0) {
            if (siz[r1] == 2) {
                insert(r0, x);
            } else {
                int l = Prev(r1, x + 1), r = Next(r1, x - 1);
                if (r - x < x - l) {
                    ret = (ret % MOD + (abs(r - x)) % MOD) % MOD;
                    erase(r1, r);
                } else {
                    ret = (ret % MOD + (abs(x - l)) % MOD) % MOD;
                    erase(r1, l);
                }
            }
        } else {
            if (siz[r0] == 2) {
                insert(r1, x);
            } else {
                int l = Prev(r0, x + 1), r = Next(r0, x - 1);
                if (r - x < x - l) {
                    ret = (ret % MOD + (abs(r - x)) % MOD) % MOD;
                    erase(r0, r);
                } else {
                    ret = (ret % MOD + (abs(x - l)) % MOD) % MOD;
                    erase(r0, l);
                }
            }
        }
    }
    cout << ret << '\n';
    return 0;
}