Cod sursa(job #2108238)

Utilizator dariusdariusMarian Darius dariusdarius Data 18 ianuarie 2018 00:19:06
Problema Schi Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.05 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

int a[30005];
int ans[30005];

template<typename T, unsigned int startIndex=0ul>
class SegmentTree {

private:
    std::vector<T> segmTree;
    unsigned int size;

    T add(const T &left, const T &right) {
        return left + right;
    }

    template<typename GetNextItemType>
    void build(unsigned int node, unsigned int left, unsigned int right, const GetNextItemType &getNextItem) {
        if (left == right) {
            this->segmTree[node] = getNextItem();
        } else {
            unsigned int middle = left + ((right - left) >> 1);
            this->build((node << 1) + 1, left, middle, getNextItem);
            this->build((node << 1) + 2, middle + 1, right, getNextItem);
            this->segmTree[node] = this->add(this->segmTree[(node << 1) + 1], this->segmTree[(node << 1) + 2]);
        }
    }

    template<typename ChangeFuncType>
    void update(unsigned int node, unsigned int left, unsigned int right, unsigned int position, const ChangeFuncType &func) {
        if (left == right) {
            this->segmTree[node] = func(this->segmTree[node]);
        } else {
            unsigned int middle = left + ((right - left) >> 1);
            if (position <= middle) {
                this->update((node << 1) + 1, left, middle, position, func);
            } else {
                this->update((node << 1) + 2, middle + 1, right, position, func);
            }
            this->segmTree[node] = this->add(this->segmTree[(node << 1) + 1], this->segmTree[(node << 1) + 2]);
        }
    }

    T query(unsigned int node, unsigned int left, unsigned int right, unsigned int x, unsigned int y) {
        if (x <= left && right <= y) {
            return this->segmTree[node];
        } else {
            unsigned int middle = left + ((right - left) >> 1);
            if (x <= middle && y >= middle + 1) {
                T a = this->query((node << 1) + 1, left, middle, x, y);
                T b = this->query((node << 1) + 2, middle + 1, right, x, y);
                return this->add(a, b);
            }
            if (x <= middle) {
                return this->query((node << 1) + 1, left, middle, x, y);
            }
            return this->query((node << 1) + 2, middle + 1, right, x, y);
        }
    }

public:
    SegmentTree() = default;

    SegmentTree(unsigned int n) {
        this->size = n;
        this->segmTree.assign(this->size * 2, 0);
    }

    SegmentTree(const void *begin, const void *end) {
        this->size = ((const unsigned char*)begin - (const unsigned char*)end) / sizeof(T);
        this->segmTree.assign(this->size * 2, 0);
        void *it = begin;
        auto getNextItem = [&it]() {
            T aux = *((T*)it);
            it += sizeof(T);
            return aux;
        };
        this->build(0u, startIndex, startIndex + size - 1, getNextItem);
    }

    template<typename InputIterator>
    SegmentTree(const InputIterator &begin, const InputIterator &end) {
        this->size = 0;
        InputIterator it = begin;
        while (it != end) {
            ++ this->size;
            ++ it;
        }
        segmTree.assign(2 * this->size, T());
        it = begin;
        auto getNextItem = [&it]() {
            T aux = *it;
            ++ it;
            return aux;
        };
        this->build(0u, startIndex, startIndex + this->size - 1, getNextItem);
    }

    template<typename ChangeFuncType>
    void change(int position, const ChangeFuncType &func) {
        this->update(0u, startIndex, startIndex + this->size - 1, position, func);
    }

    void set(unsigned int position, const T &value) {
        this->update(0u, startIndex, startIndex + this->size - 1, position, [&value](const T &original) {
            return value;
        });
    }

    T query(unsigned int x, unsigned int y) {
        return this->query(0u, startIndex, startIndex + this->size - 1, x, y);
    }

    int kthZero(int node, int left, int right, int k) {
        if (left == right) {
            return left;
        }
        int middle = left + ((right - left) >> 1);
        int sumLeft = this->segmTree[2 * node + 1];
        int numLeft = middle + 1 - left;
        int numZeroesLeft = numLeft - sumLeft;
        if (k <= numZeroesLeft) {
            return this->kthZero(2 * node + 1, left, middle, k);
        }
        return this->kthZero(2 * node + 2, middle + 1, right, k - numZeroesLeft);
    }

    int kthZero(int k) {
        return this->kthZero(0, startIndex, startIndex + this->size - 1, k);
    }
};


int main() {
    ifstream cin("schi.in");
    ofstream cout("schi.out");
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
    }
    SegmentTree<int, 1> tree(n);

    for (int i = n; i >= 1; -- i) {
        int poz = tree.kthZero(a[i]);
        tree.set(poz, 1);
        ans[poz] = i;
    }

    for (int i = 1; i <= n; ++ i) {
        cout << ans[i] << "\n";
    }

    return 0;
}