Cod sursa(job #2505476)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 6 decembrie 2019 21:53:42
Problema Schi Scor 55
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");
const int MAXN = 30001;

int sol[MAXN], tree[4 * MAXN];

void initialize() {
    for (int i = 0; i < 4 * MAXN; ++i)
        tree[i] = -MAXN;
}

void update(int left, int right, int ind, int pos, int val) {
    if (left == right) {
        if (left == pos) {
            tree[ind] = val;
            sol[val] = pos;
        }
        else {
            if (tree[ind] == -MAXN)
                return;
            ++tree[ind];
            sol[tree[ind]] = left;
        }
        return;
    }
    int mid = left + (right - left) / 2;
    if (pos >= left && pos <= mid || tree[2 * ind] >= val)
        update(left, mid, 2 * ind, pos, val);
    if (pos > mid && pos <= right || tree[2 * ind + 1] >= val)
        update(mid + 1, right, 2 * ind + 1, pos, val);
    tree[ind] = max(tree[2 * ind], tree[2 * ind + 1]);
}

void print(int n) {
    for (int i = 1; i <= n; ++i)
        fout << sol[i] << '\n';
}

int main() {
    int n;
    fin >> n;
    initialize();
    for (int i = 1; i <= n; ++i) {
        int x;
        fin >> x;
        update(1, n, 1, i, x);
    }
    print(n);
    return 0;
}