Submission #950767

#	Time	Username	Problem	Language	Result	Execution time	Memory
950767		peterandvoi	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	115 ms	18376 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    auto v = a;
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    vector<vector<int>> pos((int) v.size());
    vector<int> st;
    for (int i = 0; i < n; ++i) {
        a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
        if (pos[a[i]].size()) {
            int L = pos[a[i]].back();
            while (st.size() && st.back() > L) {
                pos[a[st.back()]].pop_back();
                st.pop_back();
            }
        }
        pos[a[i]].emplace_back(i);
        st.emplace_back(i);
    }
    vector<int> res(n, -1);
    for (int i = 0; i < (int) v.size(); ++i) {
        for (int j : pos[i]) {
            res[j] = v[i];
        }
    }
    for (int i = n - 1; ~i; --i) {
        res[i] = res[i] == -1 ? res[i + 1] : res[i];
    }
    for (int i = 0; i < n; ++i) {
        cout << res[i] << "\n";
    }
}

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