Cod sursa(job #2230551)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 10 august 2018 16:00:02
Problema Schi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <bits/stdc++.h>
#define ll long long

using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");

const int NMAX = 30005;
int v[NMAX], aint[4 * NMAX];

void buildtree(int node, int le, int ri) {
    aint[node] = ri - le + 1;
    if(le != ri) {
        int mid = (le + ri) / 2;
        buildtree(node * 2, le, mid);
        buildtree(node * 2 + 1, mid + 1, ri);
    }
}

void update(int pos, int node, int le, int ri) {
    if(le == ri)
        aint[node] = 0;
    else {
        int mid = (le + ri) / 2;
        if(pos <= mid)
            update(pos, node * 2, le, mid);
        else
            update(pos, node * 2 + 1, mid + 1, ri);
        aint[node] = aint[node * 2] + aint[node * 2 + 1];
    }
}

int query(int from, int node, int le, int ri) {
    if(le == ri)
        return le;
    int mid = (le + ri) / 2;
    if(from <= mid && aint[node * 2])
        return query(from, node * 2, le, mid);
    return query(from, node * 2 + 1, mid + 1, ri);
}

int main() {
    int n;
    in >> n;
    for(int i = 1; i <= n; i ++)
        in >> v[i];

    buildtree(1, 1, n);
    vector<int> sol(n + 1, 0);
    for(int i = n; i >= 1; i --) {
        int nr = 0;
        for(int j = n; j > i; j --)
            if(v[j] <= v[i])
                nr ++;
        int pos = query(v[i] + nr, 1, 1, n);
        sol[pos] = i;
        cout << pos << endl;
        update(pos, 1, 1, n);
    }

    for(int i = 1; i <= n; i ++)
        out << sol[i] << "\n";
    return 0;
}