제출 #810672

#제출 시각아이디문제언어결과실행 시간메모리
810672_martynasStone Arranging 2 (JOI23_ho_t1)C++17
100 / 100
216 ms20624 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...