Cod sursa(job #1295802)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 20 decembrie 2014 11:07:32
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#define DIM 30011
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int n,P;
int v[DIM],sol[DIM];
int A[4*DIM+1];

int query(int nod,int p,int u,int a,int b){
    if(a<=p && u<=b)
        return A[nod];
    int mid=p+(u-p)/2,sum=0;
    if(a<=mid)
        sum+=query(2*nod,p,mid,a,b);
    if(b>mid)
        sum+=query(2*nod+1,mid+1,u,a,b);
    return sum;
}

void update(int nod,int p,int u){
    if(p==u){
        A[nod]=1;
        return;
    }
    int mid=p+(u-p)/2;
    if(P<=mid)
        update(2*nod,p,mid);
    else
        update(2*nod+1,mid+1,u);
    A[nod]=A[2*nod]+A[2*nod+1];
}

int main(void){
    register int i,j;
    int x;

    f>>n;
    for(i=1;i<=n;i++) f>>v[i];

    for(i=n;i>0;i--){
        x=query(1,1,n,1,v[i]);
        while(x!=0){
            v[i]+=x;
            x=query(1,1,n,v[i]-x+1,v[i]);
        }
        sol[v[i]]=i;
        P=v[i];
        update(1,1,n);
    }
    for(i=1;i<=n;i++)
        g<<sol[i]<<"\n";
    f.close();
    g.close();
    return 0;
}