Cod sursa(job #2146138)

Utilizator CammieCamelia Lazar Cammie Data 27 februarie 2018 20:21:16
Problema Schi Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>

#define MAXN 30005

using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

int N, aib[MAXN * 4], v[MAXN], sol[MAXN];

inline void Update(int poz) {
    for (int i = poz; i <= N; i += i & (-i)) {
        aib[i] += 1;
    }
}

inline int Query(int a, int b) {
    int s = 0;

    for (int i = b; i; i -= i & (-i)) {
        s += aib[i];
    }

    for (int i = a - 1; i; i -= i & (-i)) {
        s -= aib[i];
    }
    return s;
}

inline void Read() {
    int query = 0, s, aux1, aux2;

    fin >> N;

    for (int i = 1; i <= N; i++) {
        fin >> v[i];
    }

    for (int i = N; i; i--) {
        aux1 = 1; aux2 = v[i]; s = v[i];
        do {
            query = Query(aux1, aux2);
            s += query; aux1 = aux2 + 1; aux2 += query;
        }while (query);
        v[i] = s;
        sol[v[i]] = i;

        Update(v[i]);
    }

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

int main () {
    Read();

    fin.close(); fout.close(); return 0;
}