Submission #937541

#	Time	Username	Problem	Language	Result	Execution time	Memory
937541		zwezdinv	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	199 ms	24660 KiB

Main

#include <bits/stdc++.h>

int main() {
        std::cin.tie(nullptr)->sync_with_stdio(false);

        int n;
        std::cin >> n;
        std::vector<int> left(n);
        std::iota(left.begin(), left.end(), 0);
        std::set<int> st;
        std::map<int, int> pos;
        std::vector<int> a(n);
        for (int i = 0; i < n; ++i) std::cin >> a[i];
        for (int i = 0; i < n; ++i) {
                if (pos.count(a[i])) {
                        int j = pos[a[i]];
                        left[i] = left[j];
                        while (st.size() && *--st.end() >= j) {
                                pos.erase(a[*--st.end()]), st.erase(--st.end());
                        }
                }
                pos[a[i]] = i;
                st.insert(i);
        }
        for (int i = n - 1; i >= 0;) {
                int c = a[i];
                int j = left[i];
                while (i >= j) a[i--] = c;
        }
        for (int i = 0; i < n; ++i) {
                std::cout << a[i] << '\n';
        }
}

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