Cod sursa(job #3353945)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 12 mai 2026 19:28:51
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.07 kb
// Source: https://usaco.guide/general/io

#include <asm-generic/errno.h>
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 30000;
int aint[4 * NMAX + 1], v[NMAX + 1], a[NMAX + 1];
int sol;

void build(int node, int st, int dr) {
    if(st == dr) {
        aint[node] = 1;
    } else {
        int mid = (st + dr) / 2;
        build(2 * node, st, mid);
        build(2 * node + 1, mid + 1, dr);
        aint[node] = aint[2 * node] + aint[2 * node + 1];
    }
}

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

void query(int node, int st, int dr, int x, int y) {
    if(x <= st && dr <= y) {
        sol = sol + aint[node];
    } else {
        int mid = (st + dr) / 2;
        //[x, y]
        //[st, mid], [mid + 1, dr]
        if(x <= mid) {
            query(2 * node, st, mid, x, y);
        }
        if(mid + 1 <= y) {
            query(2 * node + 1, mid + 1, dr, x, y);
        }
    }
}

int main() {
    ifstream cin("schi.in");
    ofstream cout("schi.out");
	int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    build(1, 1, n);
    for(int i = n; i >= 1; i--) {
        //gasim prefixul de suma v[i]
        int st = 1;
        int dr = n;
        int pos = 0;
        while(st <= dr) {
            int mid = (st + dr) / 2;
            sol = 0;
            query(1, 1, n, 1, mid);
            if(sol == v[i]) {
                pos = mid;
                dr = mid - 1;
            } else {
                if(sol > v[i]) {
                    dr = mid - 1;
                } else {
                    st = mid + 1;
                }
            }
        }
        a[pos] = i;
        //cout << pos << '\n';
        //if(pos > 0) {
        update(1, 1, n, pos);
        //}
    }
    for(int i = 1; i <= n; i++) {
        cout << a[i] << '\n';
    }
}