Cod sursa(job #648628)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 13 decembrie 2011 21:22:37
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include<fstream>
#define inf "schi.in"
#define outf "schi.out"
#define NMax 30010
#define Dim 65536
using namespace std;

fstream f(inf, ios::in), g(outf, ios::out);

int N, v[NMax], sol[NMax];
int A[4*NMax], m, pos, val, ans;

void buildTree(int n, int left, int right) {
    if( left==right ) {
        A[n] = 1;
        return;
    }

    m = (left+right)/2;
    buildTree(2*n, left, m);
    buildTree(2*n+1, m+1, right);

    A[n] = A[2*n] + A[2*n+1];
}

void query(int n, int left, int right, int p) { // => pos
    if( left==right ) {
        ans = left;
        return;
    }

    m = (left+right)/2;
    if( p<=A[2*n] ) query(2*n, left, m, p);
    else query(2*n+1, m+1, right, p-A[2*n]);
}

void update(int n, int left, int right) {//pos, val
    if( left==right ) {
        A[n] += val;
        return;
    }

    m = (left+right)/2;
    if( pos<=m ) update(2*n, left, m);
    else update(2*n+1, m+1, right);

    A[n] = A[2*n] + A[2*n+1];
}

int main()
{
    f>>N;
    for(int i=1; i<=N; i++) { f>>v[i]; pos = i; val = 1; update(1,1,N); }
    //buildTree(1, 1, N);
    //g<<A[1]<<" "<<A[2]<<" "<<A[3]<<endl;

    for(int i=N; i>=1; i--) {
        query(1, 1, N, v[i]);
        pos = ans;
        sol[pos] = i; val = -1;
        update(1, 1, N);
    }

    for(int i=1; i<=N; i++) {
        g<< sol[i] <<"\n";
    }

	f.close(); g.close();
	return 0;
}