POJ 2828

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 #define N 200010
 6 #define L ls,x,mid
 7 #define R rs,mid+1,y
 8 int sum[N<<2],order[N];
 9 void build(int cur,int x,int y)
10 {
11     int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;
12     sum[cur]=y-x+1;
13     if(x==y) return;
14     build(L);
15     build(R);
16 }
17 int query(int cur,int x,int y,int k)
18 {
19     int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;
20     if(x==y) return x;
21     if(sum[ls]>=k) return query(L,k);
22     else return query(R,k-sum[ls]);
23 }
24 void update(int cur,int x,int y,int m)
25 {
26     int mid=(x+y)/2,ls=cur<<1,rs=cur<<1|1;
27     sum[cur]--;
28     if(x==y) return;
29     if(m<=mid) update(L,m);
30     else update(R,m);
31 }
32 int main()
33 {
34     int n,pos[N],val[N];
35     while(~scanf("%d",&n)){
36         for(int i=1;i<=n;i++) scanf("%d%d",&pos[i],&val[i]);
37         build(1,1,n);
38         for(int i=n;i>=1;i--){
39             int ans=query(1,1,n,pos[i]+1);
40             order[ans]=val[i];
41             update(1,1,n,ans);
42         }
43         printf("%d",order[1]);
44         for(int i=2;i<=n;i++) printf(" %d",order[i]);
45         puts("");
46     }
47     return 0;
48 }