pku2828.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 74 行

#include <stdio.h>
#include <string.h>
#define size 200010

typedef struct Node
{
	int l, r, cnt;
} Node;

Node tree[size * 4];
int ans[size];
int pos[size], id[size];
int N;

void CreateSegmentTree(int s, int e, int p)
{
	int mid;
	tree[p].l = s;
	tree[p].r = e;
	tree[p].cnt = e - s;
	if (e - s == 1)
		return;
	mid = (s + e) >> 1;
	CreateSegmentTree(s, mid, (p << 1) + 1);
	CreateSegmentTree(mid, e, (p << 1) + 2);
}

void Set(int q, int ID, int p)
{
	tree[p].cnt--;
	if (tree[p].r - tree[p].l == 1)
	{
		ans[tree[p].l] = ID;
		return;
	}
	if (q < tree[(p << 1) + 1].cnt)
	{
		Set(q, ID, (p << 1) + 1);
	}
	else
	{
		Set(q - tree[(p << 1) + 1].cnt, ID, (p << 1) + 2);
	}
}

void Solve()
{
	int i;
	memset(ans, 0, sizeof(ans));
	CreateSegmentTree(0, N, 0);
	for (i = 0; i < N; i++)
	{
		scanf("%d %d", &pos[i], &id[i]);
	}
	for (i = N - 1; i >= 0; i--)
	{
		Set(pos[i], id[i], 0);
	}
	for (i = 0; i < N; i++)
	{
		printf("%d ", ans[i]);
	}
	printf("\n");
}

int main()
{
	int i;
	while (EOF != scanf("%d", &N))
		Solve();
	return 0;
}