제출 #895519

#제출 시각아이디문제언어결과실행 시간메모리
895519LiuBruhStone Arranging 2 (JOI23_ho_t1)C++17
0 / 100
2 ms10844 KiB
#include <bits/stdc++.h> #define int long long #define sz(v) (int)v.size() using namespace std; const int maxn = (int)2e5 + 5; const int INF = (int)1e18 + 5; struct Node { int l, r, val; }; int n; int ar[maxn]; set<int> st[maxn]; vector<Node> an; unordered_map<int, int> revans; void hehe() { vector<int> tmp; for (int i = 1; i <= n; i++) { tmp.push_back(ar[i]); } sort(tmp.begin(), tmp.end()); tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin()); for (int i = 1; i <= n; i++) { int x = lower_bound(tmp.begin(), tmp.end(), ar[i]) - tmp.begin() + 1; revans[x] = ar[i]; ar[i] = x; } } void solve() { cin >> n; for (int i = 1; i <= n; i++) cin >> ar[i]; hehe(); for (int i = 1; i <= n; i++) { int x = ar[i]; if (sz(st[x]) != 0) { int p = *st[ar[i]].rbegin(); st[ar[i]].erase(p); while (an.back().l >= p) { auto [ql, qr, qx] = an.back(); an.pop_back(); st[qx].erase(qr); } st[ar[i]].insert(i); an.push_back({p, i, ar[i]}); } else { st[ar[i]].insert(i); an.push_back({i, i, ar[i]}); } } for (auto [ql, qr, qx] : an) { for (int i = ql; i <= qr; i++) { cout << revans[qx] << '\n'; } } } /* 6 1 2 1 2 3 2 10 1 1 2 2 1 2 2 1 1 2 */ signed main() { ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...