2018年03月17日 ⁄ 综合 ⁄ 共 1250字 ⁄ 字号 评论关闭

//10736K
1641MS

#include <stdio.h>
#define L(x) (x<<1)
#define R(x) ((x<<1)+1)
#define M 200050
int loc[M],k;
struct tree
{
int
l,r;
int
val,pos;//pos表示当点有多少空位
}node[3*M];
struct data
{
int
pos,num;
}pep[M];

void BuildTree(int left,int right,int u)
{
node[u].l =
left;
node[u].r =
right;
if (left ==
right)
{

node[u].pos = 1;

return ;
}
int mid =
(left + right)>>1;

BuildTree(left,mid,L(u));

BuildTree(mid+1,right,R(u));
node[u].pos
= node[L(u)].pos + node[R(u)].pos;
}

void updata (int val,int pos,int u)
{
if
(node[u].l == node[u].r)
{

node[u].val = val;

node[u].pos = 0;

return ;
}
if
(node[L(u)].pos > pos)

updata (val,pos,L(u));
else

updata (val,pos - node[L(u)].pos,R(u));
node[u].pos
= node[L(u)].pos + node[R(u)].pos;
}

void query (int u)
{
if
(node[u].l == node[u].r)
{

loc[k++] = node[u].val;

return ;
}
query
(L(u));
query
(R(u));
}
int main ()
{
int
n,i;
while
(~scanf ("%d",&n))
{

k = 0;

for (i = 0;i < n;i ++)

scanf ("%d
%d",&pep[i].pos,&pep[i].num);

BuildTree(1,n,1);

for (i = n-1;i >= 0;i --)

updata (pep[i].num,pep[i].pos,1);

query (1);

for (i = 0;i < n - 1;i ++)

printf ("%d ",loc[i]);

printf ("%d\n",loc[n-1]);
}
return
0;
}