| 比赛 | 
    树状数组练习 | 
    评测结果 | 
    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
}