POJ2828 (C)

poj2828.c

#include <stdio.h>

#define maxn 200010

int a[maxn];

struct segment {
    int left,right,count;
} tree[maxn*3];

void tree_create(int p, int l, int r) {
    tree[p].left=l;
    tree[p].right=r;
    tree[p].count=r-l+1;
    if (tree[p].count==1) return;
    int m=(l+r)>>1;
    tree_create(p*2,l,m);
    tree_create(p*2+1,m+1,r);
}

void tree_insert(int p, int pos, int val) {
    if (tree[p].left==tree[p].right) {
        tree[p].count--;
        a[tree[p].left]=val;
        return;
    }
    if (tree[p*2].count>=pos) tree_insert(p*2,pos,val); else tree_insert(p*2+1,pos-tree[p*2].count,val);
    tree[p].count=tree[p*2].count+tree[p*2+1].count;
}

int main() {
    int n,pos[maxn],val[maxn];
    while(~scanf("%d",&n)) {
        for (int i=1; i<=n; i++) scanf("%d%d",&pos[i],&val[i]);
        tree_create(1,0,n+1);
        for (int i=n; i>=1; i--) tree_insert(1,pos[i]+1,val[i]);
        for (int i=0; i<n-1; i++) printf("%d ",a[i]);
        printf("%d\n",a[n-1]);
    }
    return 0;
}