POJ2182 (C) && Differences between poj2828.c & poj2182.c

poj2182.c

#include <stdio.h>

#define maxn 8010

int a[maxn],used[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[val]=tree[p].left;
        used[a[val]]=1;
        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,i,pos[maxn];
    scanf("%d",&n);
    for (i=2; i<=n; i++) scanf("%d",&pos[i]);
    tree_create(1,1,n);
    for (i=n; i>=2; i--) tree_insert(1,pos[i]+1,i);
    for (i=1; i<=n; i++) if (!used[i]) break;
    a[1]=i;
    for (i=1; i<=n; i++) printf("%d\n",a[i]);
    return 0;
}

tmp.diff

3c3
< #define maxn 8010
---
> #define maxn 200010
5c5
< int a[maxn],used[maxn];
---
> int a[maxn];
24,25c24
<         a[val]=tree[p].left;
<         used[a[val]]=1;
---
>         a[tree[p].left]=val;
33,40c32,39
<     int n,i,pos[maxn];
<     scanf("%d",&n);
<     for (i=2; i<=n; i++) scanf("%d",&pos[i]);
<     tree_create(1,1,n);
<     for (i=n; i>=2; i--) tree_insert(1,pos[i]+1,i);
<     for (i=1; i<=n; i++) if (!used[i]) break;
<     a[1]=i;
<     for (i=1; i<=n; i++) printf("%d\n",a[i]);
---
>     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]);
>     }