Submission #776933

#TimeUsernameProblemLanguageResultExecution timeMemory
776933ind1vStone Arranging 2 (JOI23_ho_t1)C++11
100 / 100
173 ms35656 KiB
#include <bits/stdc++.h> using namespace std; const int N = 200005; int n; int a[N]; vector<int> v; set<int> idx[N]; set<int> indices; int l[N], ans[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } copy(a + 1, a + n + 1, back_inserter(v)); sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); for (int i = 1; i <= n; i++) { a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin(); if (!idx[a[i]].empty()) { int lst = *idx[a[i]].rbegin(); vector<int> removals; for (auto it = indices.upper_bound(lst); it != indices.end(); it++) { idx[a[*it]].erase(*it); removals.emplace_back(*it); } for (auto &x : removals) { indices.erase(x); } l[i] = lst; } else { l[i] = i; } idx[a[i]].insert(i); indices.insert(i); } for (int i = n, j = n; i >= 1; i--) { while (j >= l[i]) { ans[j--] = a[i]; } } for (int i = 1; i <= n; i++) { cout << v[ans[i]] << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...