Cod sursa(job #1248383)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 25 octombrie 2014 00:50:42
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 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;
}