Submission #782347

#	Time	Username	Problem	Language	Result	Execution time	Memory
782347		thimote75	Stone Arranging 2 (JOI23_ho_t1)	C++14	100 / 100	420 ms	153592 KiB

Main

#include <bits/stdc++.h>

using namespace std;

template <typename T>
struct SGD {
    bool _update = false;
    T value;
};
template<typename T>
struct SetTree {
    vector<SGD<T>> tree;

    int start, height, size;
    SetTree (int _size, T def) {
        size = _size;
        height = ceil(log2(size));
        start = 1 << height;
        tree.resize(start << 1);

        for (auto &pos : tree) pos.value = def;
    }
    void _update (int id) {
        if (id == 0) return ;
        _update(id >> 1);

        if (id >= start || (!tree[id]._update)) return;
        tree[2 * id    ].value = tree[id].value;
        tree[2 * id + 1].value = tree[id].value;
        tree[2 * id    ]._update = true;
        tree[2 * id + 1]._update = true;
        tree[id]._update = false;
    }
    void update (int id) {
        id += start;
        _update(id);
    }
    T get (int id) {
        update(id);

        return tree[id + start].value;
    }
    void set (int i, T val) {
        _update(i);
        tree[i].value   = val;
        tree[i]._update = true;
    }
    void set (int l, int r, T val) {
        l += start; r += start;

        while (l < r) {
            if ((l & 1) == 1) set(l, val);
            if ((r & 1) == 0) set(r, val);
            l = (l + 1) >> 1;
            r = (r - 1) >> 1;
        }

        if (l == r) set (l, val);
    }
    void show () {
        for (int h = 0; h <= height; h ++) {
            int v = 1 << h;
            for (int s = 0; s < v; s ++)
                cout << tree[s + v].value << ":" << tree[s + v]._update << " ";

            cout << endl;
        }
    }
};

using idqgr = map<int, deque<int>>;

int main () {
    int N;
    cin >> N;

    SetTree<bool> tree(N, false);
    idqgr queue;
    SetTree<int> answer(N, 0);

    for (int i = 0; i < N; i ++) {
        int a; cin >> a;

        if (queue.find(a) == queue.end())
            queue.insert({ a, {} });
        deque<int> &positions = (*queue.find(a)).second;

        positions.push_back(i);
        while (tree.get(positions.front()))
            positions.pop_front();
        
        int left = positions.front();

        tree.set(left + 1, i - 1, true);
        answer.set(left, i, a);
    }

    for (int i = 0; i < N; i ++) cout << answer.get(i) << "\n";
}

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40