记录编号	555606	评测结果	AAAAAAAAAA
题目名称	[POJ 2828]排队买票	最终得分	100
用户昵称	fsdh	是否通过	通过
代码语言	C++	运行时间	0.177 s
提交时间	2020-10-08 22:03:04	内存使用	6.14 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 2e5 + 10;
struct node {
	int l ,r ,sum;
	node () {
		l = r = sum = 0;
	}
}tree[MAXN << 2];
int ans[MAXN];
void pushup (int i) {
	tree[i].sum = tree[i << 1].sum + tree[i << 1 | 1].sum;
	return ;
}
void build (int i ,int l ,int r) {
	tree[i].l = l ,tree[i].r = r;
	if (l == r) {//设置为空闲位置 
		tree[i].sum = 1;
		return ;
	}
	int mid = (l + r) >> 1;
	build (i << 1 ,l ,mid);
	build (i << 1 | 1 ,mid + 1 ,r);
	pushup (i);
	return ;
}
void insert (int i ,int p ,int v) {
	int l = tree[i].l ,r = tree[i].r;
	if (l == r) {
		ans[l] = v;
		tree[i].sum = 0;
		return ;
	}
	int mid = (l + r) >> 1;
	if (p <= tree[i << 1].sum) insert (i << 1 ,p ,v);
	else insert (i << 1 | 1 ,p - tree[i << 1].sum ,v);
	pushup (i);
	return ;
}
int n;
int main () {
	freopen ("buytickets.in","r",stdin);
	freopen ("buytickets.out","w",stdout);
	while (scanf ("%d",&n) != EOF) {
		int p[MAXN] ,v[MAXN];
		build (1 ,1 ,n);
		for (int q = 1;q <= n;++ q) {
			scanf ("%d%d",&p[q] ,&v[q]);
		}
		for (int q = n;q >= 1;-- q) {
			insert (1 ,p[q] + 1 ,v[q]);
		}
		for (int q = 1;q <= n;++ q) {
			printf ("%d ",ans[q]);
		}
		printf ("\n");
	}
	return 0;
}