Cod sursa(job #2067044)

Utilizator CammieCamelia Lazar Cammie Data 15 noiembrie 2017 19:38:20
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <cstring>

#define MAXN 30005
#define inf 0x3f3f3f3f

using namespace std;

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

int p[MAXN], sol[MAXN], ait[MAXN * 3], n;

inline void Read() {
    fin >> n;

    for (int i = 1; i <= n; i++)
        fin >> p[i];
}

inline void Update(int poz, int st, int dr, int a, int val) {
    int mij = (st + dr) / 2;

    if (st == dr && st == a) {
        sol[st] = val;
        ait[poz] = 1;
    }
    else {
        if (ait[poz * 2] + a <= mij) { ///daca toate valorile adaugate in ramura din stanga nu depasesc ranking-ul "real" al elementului curent
            Update(poz * 2, st, mij, a, val);
        }
        else ///Raspunsul se afla pe ramura din dreapta
            Update(poz * 2 + 1, mij + 1, dr, a + ait[poz * 2], val);
        ait[poz] = ait[poz * 2] + ait[poz * 2 + 1]; ///nr de elemente adaugate in subarborele cu radacina in poz
    }
}

inline void Solve() {
    for (int i = n; i; i--) {
        Update(1, 1, n, p[i], i);
    }
}

inline void Write() {
    for (int i = 1; i <= n; i++)
        fout << sol[i] << "\n";
}

int main () {
    Read();
    Solve();
    Write();

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