Cod sursa(job #3247897)

Utilizator AndreiDragosDavidDragos Andrei David AndreiDragosDavid Data 9 octombrie 2024 18:39:32
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;

class BIT {
private:
    vector<int> tree;
    int n;

public:
    BIT(int size){
        n=size;
        tree.resize(n+1, 0);
    }

    void update(int idx, int val){
        while(idx<=n){
            tree[idx]+=val;
            idx+= idx & (-idx);
        }
    }

    int query(int idx){
        int ans=0;
        while(idx>0){
            ans+=tree[idx];
            idx-= idx & (-idx);
        }

        return ans;
    }
};

int n;
vector<int> posInt, ans;

int32_t main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
#endif
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n; posInt.resize(n);
    ans.resize(n);

    for(auto& it : posInt)
        cin >> it;

    BIT bit(n);

    for(int i=n-1; i>=0; --i){
        int current = posInt[i];

        int lo=1, hi=n;

        while(lo < hi){
            int mid = (lo+hi)/2;

            if(mid-bit.query(mid)<current)
                lo=mid+1;
            else
                hi=mid;
        }

        ans[lo-1] = i+1;
        bit.update(lo, 1);
    }

    for(auto& it : ans) cout << it << '\n';

    return 0;
}