Cod sursa(job #3375276)

Utilizator cristiz123456Zoescu Cristian cristiz123456 Data 11 noiembrie 2026 12:06:16
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <bits/stdc++.h>

using namespace std;
const int N = 30000;
struct {
    int n, tree[4 * N + 1];
    void init(int n) {
        this->n = n;
    }
    void update(int nod, int st, int dr, int val, int poz) {
        if(st == dr) {
            tree[nod] = val;
            return;
        }
        int mij = (st + dr) / 2;
        if(poz <= mij) {
            update(2 * nod, st, mij, val, poz);
        }
        else {
            update(2 * nod + 1, mij + 1, dr, val, poz);
        }
        tree[nod] = tree[2 * nod] + tree[2 * nod + 1];
    }
    void update(int val, int poz) {
        update(1, 1, n, val, poz);
    }
    void query(int nod, int st, int dr, int a, int b, int &rez) {
        if(a <= st && dr <= b) {
            rez += tree[nod];
            return;
        }
        int mij = (st + dr) / 2;
        if(a <= mij) {
            query(2 * nod, st, mij, a, b, rez);
        }
        if(b > mij) {
            query(2 * nod + 1, mij + 1, dr, a, b, rez);
        }
    }
    int query(int a, int b) {
        int rez = 0;
        query(1, 1, n, a, b, rez);
        return rez;
    }
} aint;
int v[N + 1], clasament[N + 1];
int main()
{
    ifstream cin("schi.in");
    ofstream cout("schi.out");
    int n, i;
    cin >> n;
    aint.init(n);
    for(i = 1; i <= n; i++) {
        cin >> v[i];
    }
    for(i = n; i > 0; i--) {
        int pozfinal, st, dr, mij, pozinit = v[i];
        st = 0;
        dr = n;
        while(dr - st > 1) {
            mij = (st + dr) / 2;
            if(pozinit + aint.query(1, mij) <= mij)
                dr = mij;
            else
                st = mij;
        }
        pozfinal = dr;
        //printf("%d %d %d\n", pozfinal, pozinit + aint.query(1, 3), pozinit + aint.query(1, pozfinal));
        clasament[pozfinal] = i;
        aint.update(1, pozfinal);
    }
    for(i = 1; i <= n; i++) {
        cout << clasament[i] << "\n";
    }
    return 0;
}