Cod sursa(job #3142201)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 20 iulie 2023 09:44:19
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
typedef long long ll;
typedef pair<int, int> pi;
int t, T;

void update(vector<int>& tree, int nod, int tl, int tr, int poz) {
    if (tl == tr && tl == poz) {
        tree[nod]++;
        return;
    }

    int tm = (tl + tr) / 2;
    if (poz <= tm)
        update(tree, 2 * nod, tl, tm, poz);
    else
        update(tree, 2 * nod + 1, tm + 1, tr, poz);
    tree[nod] = tree[2 * nod] + tree[2 * nod + 1];
}

int query(vector<int>& tree, int nod, int tl, int tr, int l, int r) {

    if (l > r)
        return 0;

    if (tl == l && tr == r) {
        return tree[nod];
    }

    int tm = (tl + tr) / 2;
    return query(tree, 2 * nod, tl, tm, l, min(tm, r)) +
        query(tree, 2 * nod + 1, tm + 1, tr, max(tm + 1, l), r);
}

int solve(vector<int>& tree, vector<int>& ans, int n, int y) {
    //cout << "--------------------- " << n << " ---------------  " << y << '\n';
    int left = 1, right = n;
    int ans_rk = -1;
    while (left <= right) {
        int mij = (left + right) / 2;
        int prefix = query(tree, 1, 1, n, 1, mij);
        //cout << left << ' ' << mij << ' ' << right << ' ' << prefix << ' ' << y << ' ' << mij - prefix << '\n';
        if (mij - prefix < y) {
            left = mij + 1;
        }
        else
            if (mij - prefix >= y) {
                if (ans[mij] == -1 && mij - prefix == y) {
                    ans_rk = mij;
                }
                right = mij - 1;
            }
    }

    return ans_rk;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    f >> n;
    vector < int > tree(4 * n), rank_init(n + 1), ans(n + 1, -1);
    for (int i = 1; i <= n; i++) {
        f >> rank_init[i];
    }

    for (int i = n ; i >= 1; i--) {
        int final_rank = solve(tree, ans, n, rank_init[i]);
        //cout << "*****2222*0000 " << i << ' ' << final_rank << '\n';
        ans[final_rank] = i;
        //cout << "****** " << i << ' ' << ans[i] << '\n';
        update(tree, 1, 1, n, final_rank);

        //cout << "sdddddddddddd\n";
    }

    for (int i = 1; i <= n; i++) g << ans[i] << '\n';

    return 0;
}