Submission #782343

#	Time	Username	Problem	Language	Result	Execution time	Memory
782343		thimote75	Stone Arranging 2 (JOI23_ho_t1)	C++14	25 / 100	2076 ms	1748 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct StatusTree {
    vector<bool> status;

    StatusTree (int size) {
        status.resize(size, false);
    }
    bool get (int id) {
        return status[id];
    }
    void setTrue (int l, int r) {
        for (int i = l; i <= r; i ++) status[i] = true;
    }
};
struct SetTree {
    vector<int> answer;
    SetTree (int size) {
        answer.resize(size);
    }
    void set (int l, int r, int v) {
        for (int i = l; i <= r; i ++) answer[i] = v;
    }
};

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



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

    StatusTree tree(N);
    idqgr queue;
    SetTree answer(N);

    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.setTrue(left + 1, i - 1);
        answer.set(left, i, a);
    }

    for (int u : answer.answer) cout << u << "\n";
}

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