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