样例RE求助qwq
  • 板块P2073 送花
  • 楼主Lian_zy
  • 当前回复12
  • 已保存回复12
  • 发布时间2024/6/9 11:08
  • 上次更新2024/6/9 14:53:49
查看原帖
样例RE求助qwq
923248
Lian_zy楼主2024/6/9 11:08
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1e5 + 10;
bool is[maxn];
int n, x, w, c, op, ans, pri, now, tot, root;
struct npde {
	int l, r, b, rd, val, size;
} t[maxn];
void push_up(int now) {
	t[now].size = t[t[now].l].size + t[t[now].r].size + 1;
	return ;
}
void spilt(int now, int key, int &x, int &y) {
	if (now) {
		if (t[now].val <= key) {
			x = now;
			spilt(t[now].r, key, t[now].r, y);
		} else {
			y = now;
			spilt(t[now].l, key, x, t[now].l);
		}
		push_up(now);
	} else x = y = 0;
	return ;
}
int merge(int x, int y) {
	if (x && y) {
		if (t[x].rd <= t[y].rd) {
			t[x].r = merge(t[x].r, y);
			push_up(x);
			return x;
		} else {
			t[y].l = merge(x, t[y].l);
			push_up(y);
			return y;
		}
	}
	return x + y;
}
int new_node(int key, int b) {
	tot++;
	is[b] = true;
	t[tot].b = b;
	t[tot].l = t[tot].r = 0;
	t[tot].val = key;
	t[tot].size = 1;
	t[tot].rd = rand();
	return tot;
}
void insert(int key, int b) {
	int x, y;
	spilt(root, key, x, y);
	root = merge(merge(x, new_node(key, b)), y);
	return ;
}
void del(int key) {
	int x, y, z;
	spilt(root, key, x, y);
	spilt(x, key - 1, x, z);
	is[t[z].val] = false;
	z = merge(t[z].l, t[z].r);
	root = merge(merge(x, z), y);
	now--;
	return ;
}
int get_rank(int key) {
	int x, y;
	spilt(root, key - 1, x, y);
	int ans = t[x].size + 1;
	root = merge(x, y);
	return ans;
}
int get_key(int now, int k) {
	int cnt = t[t[now].l].size + 1;
	if (cnt == k) return t[now].val;
	else if (cnt < k) return get_key(t[now].r, k - cnt);
	return get_key(t[now].l, k);
}
int add(int now, int k) {
	int cnt = t[t[now].l].size + 1;
	if (cnt == k) return t[now].b;
	else if (cnt < k) return get_key(t[now].r, k - cnt);
	return get_key(t[now].l, k);
}
int main() {
	scanf("%d", &op);
	while (~op) {
		if (op == 1) {
			scanf("%d %d", &w, &c);
			if (is[c]) continue;
			insert(w, c);
		} else if (op == 2) del(get_key(root, 1));	
		else if (op == 3) del(get_key(root, now));
		scanf("%d", &op);
	}
	while (now) {
		ans += add(root, 1);
		pri += get_key(root, 1);
		del(get_key(root, 1));
	}
	printf("%d %d\n", ans, pri);
	return 0;
}
2024/6/9 11:08
加载中...