Cod sursa(job #3354741)

Utilizator AndreiNicolaescuEric Paturan AndreiNicolaescu Data 20 mai 2026 09:49:20
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <bits/stdc++.h>
#define cin ci
#define cout co
using namespace std;
ifstream cin("schi.in");
ofstream cout("schi.out");
const int nmax = 30000;
int n;
vector<int> v;
int tree[4 * nmax + 5];

void build(int node, int left, int right)
{
    if(left == right)
    {
        tree[node] = 1;
        return;
    }
    int mij  = (left + right) / 2;
    build(2 * node, left, mij);
    build(2 * node + 1, mij + 1, right);

    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

void update(int node, int left, int right, int pos)
{
    if(left == right)
    {
        tree[node] = 0;
        return;
    }
    int mij = (left + right) / 2;
    if(pos <= mij)
        update(2 * node, left, mij, pos);
    else
        update(2 * node + 1, mij + 1, right, pos);

    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

int pos = 0;
void query(int node, int left, int right, int kth)
{
    if(left == right)
    {
        pos = left;
        return;
    }
    int mij = (left + right) / 2;
    if(tree[2 * node] >= kth)
        query(2 * node, left, mij, kth);
    else
        query(2 * node + 1, mij + 1, right, kth - tree[2 * node]);
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> n;
    v.resize(n + 5);
    for(int i = 1; i <= n; i ++)
        cin >> v[i];

    build(1, 1, n);

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

    for(int i = 1; i <= n; i ++)
        cout << res[i] << " ";

    return 0;
}