Cod sursa(job #3042177)

Utilizator moldovan_robert_lolMoldovan Robert moldovan_robert_lol Data 4 aprilie 2023 13:17:35
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
// schi
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

std::ifstream fin("schi.in");
std::ofstream fout("schi.out");

template<class T>
class FenwickTree {
private:
    std::vector<T> bit;
public:
    FenwickTree(int size = 0) {
        bit.assign(size,0);
    }

    void assign(int size = 0) {
        bit.assign(size,0);
    }

    void init(std::vector<int> &arr) {
        bit.assign(arr.size(),0);
        for (int i = 1; i < arr.size(); i++) {
            bit[i] += arr[i];
            if (i+(i&-i)<arr.size()) bit[i+(i&-i)] += bit[i];
        }
    }

    void add(int poz, T val) {
        while (poz<bit.size()) {
            bit[poz] += val;
            poz += poz&-poz;
        }
    }

    T query(int poz) {
        T ret = 0;
        while (poz) {
            ret += bit[poz];
            poz ^= poz&-poz;
        }
        return ret;
    }

    T query(int l, int r) {
        return query(r) - query(l-1);
    }

    int binary_lifting(T val) {
        int ret = 0;
        for (int step = (1<<20); step; step >>= 1) {
            if (ret+step>bit.size()) continue;
            if (bit[ret+step]<val) {
                val -= bit[ret+step];
                ret = ret+step;
            }
        }
        return ret+1;
    }
};

int x;
int arr[30005];
int ret[30005];

int main() {
    std::ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    fin >> x;
    FenwickTree<int> fnwk(x+1);

    for (int i = 1; i <= x; i++) {
        fin >> arr[i];
        fnwk.add(i,1);
    }

    for (int i = x; i >= 1; i--) {
        int poz = fnwk.binary_lifting(arr[i]);
        fnwk.add(poz,-1);
        ret[poz] = i;
    }

    for (int i = 1; i <= x; i++) {
        fout << ret[i] << "\n";
    }
}