学步园

//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;
}