Cod sursa(job #3130066)

Utilizator annna7Pecheanu Anna annna7 Data 16 mai 2023 19:13:13
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>

#define NMAX 30000

using namespace std;

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

int ST[4 * NMAX];

void build(int node, int l, int r) {
    if (l == r) {
        ST[node] = 1;
    } else {
        int middle = (l + r) / 2;
        build(2 * node + 1, l, middle);
        build(2 * node + 2, middle + 1, r);
        ST[node] = ST[2 * node + 1] + ST[2 * node + 2];
    }
}

int query(int node, int l, int r, int k) {
    if (l == r) {
        return l;
    }
    int middle = (l + r) / 2;
    if (k <= ST[2 * node + 1]) {
        return query(2 * node + 1, l, middle, k);
    } else {
        return query(2 * node + 2, middle + 1, r, k - ST[2 * node + 1]);
    }
}

void update(int node, int l, int r, int arrayIndex) {
    if (l == r) {
        ST[node] = 0;
    }
    else {
        int middle = (l + r) / 2;
        if (arrayIndex <= middle) {
            update(2 * node + 1, l, middle, arrayIndex);
        } else {
            update(2 * node + 2, middle + 1, r, arrayIndex);
        }
        ST[node] = ST[2 * node + 1] + ST[2 * node + 2];
    }
}

int main()
{
    int n;
    fin >> n;

    build(0, 0, n - 1);

    vector <int> pos(n);
    for (int i = 0; i < n; ++i) {
        fin >> pos[i];
    }

    vector <int> ans(n);
    for (int i = n - 1; i >= 0; --i) {
        int k = query(0, 0, n - 1, pos[i]);
        update(0, 0, n - 1, k);
        ans[k] = i + 1;
    }

    for (int i = 0; i < n; ++i) {
        fout << ans[i] << '\n';
    }

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