제출 #978192

#제출 시각아이디문제언어결과실행 시간메모리
978192asdfgraceStone Arranging 2 (JOI23_ho_t1)C++17
100 / 100
58 ms16200 KiB
#include <bits/stdc++.h> using namespace std; #define dbg(x) x #define prt(x) dbg(cerr << x) #define pv(x) dbg(cerr << #x << " = " << x << '\n') #define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n') #define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");) #define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << " "); prt("}\n");) #define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n')); #define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n')); /* if said elem has a previous occurrence delete ranges from the array and decrease the counts until you get to the previous occurrence and extend the right bound from there to i else you just add a range of length 1 ending at i and increase the cnt by 1 */ int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<int> ord(n); iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&] (int x, int y) { return a[x] < a[y]; }); vector<int> b(n), val(1, a[ord[0]]); vector<vector<int>> at(n); int cur = 0; for (int i = 0; i < n; i++) { if (i > 0 && a[ord[i]] > a[ord[i - 1]]) { cur++; val.push_back(a[ord[i]]); } b[ord[i]] = cur; } vector<int> cnt(n, 0); vector<array<int, 3>> r; for (int i = 0; i < n; i++) { if (cnt[b[i]]) { while (r.size() && r[r.size() - 1][0] != b[i]) { cnt[r[r.size() - 1][0]]--; r.pop_back(); } assert(r.size() && r[r.size() - 1][0] == b[i]); r[r.size() - 1][2] = i; } else { cnt[b[i]]++; r.push_back({b[i], i, i}); } } for (auto [k, lb, rb] : r) { for (int i = lb; i <= rb; i++) { cout << val[k] << '\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...