10pts求条

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

using namespace std;

const int N = 80000 + 5;

struct node {
	int son[2];
	
	int fa, val, sz;
} tree[N];

int n, root, num, ans, cnt;

multiset<int> st;

void pushup(int x) {
	tree[x].sz = tree[tree[x].son[0]].sz + tree[tree[x].son[1]].sz + 1;
}

bool get(int x) {
	return x == tree[tree[x].fa].son[1];
}

void rotate(int x) {
	int y = tree[x].fa, z = tree[y].fa, d = get(x);
	if (tree[x].son[d ^ 1]) tree[tree[x].son[d ^ 1]].fa = y;
	tree[y].son[d] = tree[x].son[d ^ 1];
	tree[x].son[d ^ 1] = y;
	tree[x].fa = z;
	tree[y].fa = x;
	if (z) tree[z].son[tree[z].son[1] == y] = x;
	pushup(y);
	pushup(x);
}

void splay(int x) {
	for (int f = tree[x].fa; f; rotate(x), f = tree[x].fa) 
		if (tree[f].fa) rotate(get(x) == get(f) ? f : x);
	root = x; 
}

void ins(int val) {
	if (!root) {
		tree[++num].val = val;
		root = num;
		pushup(root);
		return;
	} 
	int tmp = root, f = 0;
	while (true) {
		f = tmp;
		tmp = tree[tmp].son[tree[tmp].val < val];
		if (!tmp) {
			tree[++num].val = val;
			tree[num].fa = f;
			tree[f].son[tree[f].val < val] = num;
			pushup(num);
			pushup(f);
			splay(num);
			break;
		}
	} 
} 

int pre(void) {
	int tmp = tree[root].son[0];
	if (!tmp) {
		return tmp;
	}
	while (tree[tmp].son[1]) {
		tmp = tree[tmp].son[1];
	} 
	splay(tmp);
	return tmp;
}

int nxt(void) {
	int tmp = tree[root].son[1];
	if (!tmp) {
		return 2e11;
	} 
	while (tree[tmp].son[0]) {
		tmp = tree[tmp].son[0];
	}
	splay(tmp);
	return tmp;
}

int rnk(int val) {
	int ans = 0, tmp = root;
	while (true) {
		if (val < tree[tmp].val) {
			tmp = tree[tmp].son[0];
		} else {
			ans += tree[tree[tmp].son[0]].sz;
			if (!tmp) {
				return ans + 1;
			} 
			if (tree[tmp].val == val) {
				splay(tmp);
				return ans + 1;
			}
			ans += 1;
			tmp = tree[tmp].son[1];
		}
	}
}

void del(int val) {
	rnk(val);
	if (!tree[root].son[0]) {
		int tmp = root;
		root = tree[root].son[1];
		tree[root].fa = 0;
		tree[tmp].son[0] = tree[tmp].son[1] = tree[tmp].val = tree[tmp].fa = tree[tmp].sz = 0;
		return;
	} else if (!tree[root].son[1]) {
		int tmp = root;
		root = tree[root].son[0];
		tree[root].fa = 0;
		tree[tmp].son[0] = tree[tmp].son[1] = tree[tmp].val = tree[tmp].fa = tree[tmp].sz = 0;
		return;
	} else if (!tree[root].son[0] && !tree[root].son[1]) {
		tree[root].son[0] = tree[root].son[1] = tree[root].val = tree[root].fa = tree[root].sz = 0;
		root = 0;
		return;
	}
	int tmp = root, x = pre();
	tree[tree[tmp].son[1]].fa = x;
	tree[x].son[1] = tree[tmp].son[1];
	tree[tmp].son[0] = tree[tmp].son[1] = tree[tmp].val = tree[tmp].fa = tree[tmp].sz = 0;
	pushup(root);
}

signed main(void) {
	ins(-2e11);
	ins(2e11);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int opt, x;
		cin >> opt >> x;
		if (opt == 0) {
			ins(x);
			cnt++;
			if (!st.empty()) {
//				cout << ans << "      " << cnt << "      " << st.size() << endl;
				auto p1 = st.lower_bound(x), p2 = st.upper_bound(x);
				if (abs(x - *p1) == abs(x - *p2)) {
					ans = (ans % 1000000 + abs(x - *p1) % 100000) % 1000000;
					st.erase(p1);
				} else {
					if (abs(x - *p1) > abs(x - *p2)) {
						ans = (ans % 1000000 + abs(x - *p2) % 100000) % 1000000;
						st.erase(p2);
					} else {
						ans = (ans % 1000000 + abs(x - *p1) % 100000) % 1000000;
						st.erase(p1);
					}
				}
				del(x);
				cnt--;
//				cout << ans << "      " << cnt << "      " << st.size() << endl;
			}
		} else {
			if (cnt > 0) {
//				cout << ans << "      " << cnt << "      " << st.size() << endl;
				st.insert(x);
				ins(x);
				int p1 = pre(), p2 = nxt();
				del(x);
				if (abs(x - tree[p1].val) == abs(x - tree[p2].val)) {
					ans = (ans % 100000 + abs(x - tree[p1].val) % 1000000) % 1000000;
					del(tree[p1].val);
					cnt--;
				} else {
					if (abs(x - tree[p1].val) > abs(x - tree[p2].val)) {
						ans = (ans % 100000 + abs(x - tree[p2].val) % 1000000) % 1000000;
						del(tree[p2].val);
						cnt--;
					} else {
						ans = (ans % 100000 + abs(x - tree[p1].val) % 1000000) % 1000000;
						del(tree[p1].val);
						cnt--;
					}
				}
				st.erase(x);
//				cout << ans << "      " << cnt << "      " << st.size() << endl;
			}
		}
	} 
	cout << ans;
	return 0;
}