제출 #950767

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