比赛 树状数组练习 评测结果 AAAAAAAAAA
题目名称 排队买票 最终得分 100
用户昵称 对立猫猫对立 运行时间 0.177 s
代码语言 C++ 内存使用 4.23 MiB
提交时间 2025-06-11 21:05:26
显示代码纯文本
#include <bits/stdc++.h>
#define Tairitsu return 0;
#define lowbit(x) (x & -x)
using namespace std;
const int N = 200000;
int n, c[N + 5], ans[N + 5], t[N + 5], r[N + 5];
void add(int x, int num) {
	for (; x <= 2e5; x += lowbit(x)) c[x] += num;
}
int ask(int x) {
	int pos = 0, sum = 0;
	for (int j = 18; j >= 0; j--) {
		if (pos + (1 << j) <= n && sum + c[pos + (1 << j)] <= x) {
			pos += (1 << j);
			sum += c[pos];
		}
	}
	return pos;
}

int main() {
	freopen("buytickets.in", "r", stdin);
	freopen("buytickets.out", "w", stdout);
	while (scanf("%d", &n) != EOF) {
		for (int i = 1; i <= n; i++) add(i, 1);
		for (int i = 1; i <= n; i++) scanf("%d%d", &t[i], &r[i]);
		for (int i = n; i >= 1; i--) {
			int pos = ask(t[i]);
			pos += 1;
			ans[pos] = r[i];
			add(pos, -1);
		}
		for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
		printf("\n");
	}
	Tairitsu
}