Submission #810672

#	Time	Username	Problem	Language	Result	Execution time	Memory
810672		_martynas	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	216 ms	20624 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back

using pii = pair<int, int>;

const int mxn = 2e5+5;

int n;
int A[mxn];

int main() {
    cin >> n;
    stack<pii> st;
    set<int> S;
    for(int i = 0; i < n; i++) {
        cin >> A[i];
    }
    st.push({A[0], 0}); S.insert(A[0]);
    vector<pii> events[mxn];
    for(int i = 1; i < n; i++) {
        int j = -1;
        while(S.count(A[i])) {
            j = st.top().se;
            S.erase(st.top().fi);
            st.pop();
        }
        st.push({A[i], i});
        S.insert(A[i]);
        if(j != -1) {
            events[i].pb({A[i], j});
        }
    }
    queue<pii> Q;
    for(int i = n-1; i >= 0; i--) {
        assert(events[i].size() <= 1);
        for(auto p : events[i]) {
            Q.push(p);
        }
        while(!Q.empty() && Q.front().se > i) {
            Q.pop();
        }
        if(!Q.empty()) {
            A[i] = Q.front().fi;
        }
    }
    for(int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    return 0;
}

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