제출 #1038092

#제출 시각아이디문제언어결과실행 시간메모리
1038092SoulKnightStone Arranging 2 (JOI23_ho_t1)C++17
0 / 100
2 ms11356 KiB
#include "bits/stdc++.h" using namespace std; #define ll long long #define ln '\n' const int N = 2e5 + 5; int n, a[N], glit = 1; vector<int> vec, where[N]; #define lc (v << 1) #define rc ((v << 1) + 1) struct node{ int color; int tm = N + 5; } seg[4*N]; void pushdown(int v){ if (!seg[v].color) return; seg[rc].color = (seg[rc].tm > seg[v].tm? seg[v].color: seg[rc].color); seg[rc].tm = min(seg[rc].tm, seg[v].tm); seg[lc].color = (seg[lc].tm > seg[v].tm? seg[v].color: seg[lc].color); seg[lc].tm = min(seg[lc].tm, seg[v].tm); seg[v].color = 0; seg[v].tm = N + 5; } void upd(int v, int tl, int tr, int l, int r, int color){ if (tr < l || tl > r) return; if (l <= tl && tr <= r){ // cout << v << ' ' << tl << ' ' << tr << ' ' << color << ln; seg[v].color = color; seg[v].tm = glit; return; } pushdown(v); int tm = (tl + tr) / 2; upd(lc, tl, tm, l, r, color); upd(rc, tm+1, tr, l, r, color); } int query(int v, int tl, int tr, int p){ if (tl == tr) return (seg[v].color == 0? a[tl]: seg[v].color); pushdown(v); int tm = (tl + tr) / 2; if (p <= tm) return query(lc, tl, tm, p); else return query(rc, tm+1, tr, p); } void solve(){ cin >> n; for (int i = 1; i <= n; i++){ cin >> a[i]; vec.push_back(a[i]); } sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end()); for (int i = 1; i <= n; i++){ a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin()+1; } for (int i = 1; i <= n; i++){ // cout << "checking " << i << ' ' << a[i] << ln; while (!where[a[i]].empty()){ int last = where[a[i]].back(); int actual = query(1, 1, n, last); // cout << "looking " << last << ' ' << actual << ln; if (actual != a[i]) {where[a[i]].pop_back(); continue;} upd(1, 1, n, last, i-1, a[i]); break; } where[a[i]].push_back(i); glit++; } // for (int i = 1; i <= 4*n; i++) pushdown(i); for (int i = 1; i <= n; i++){ int t = query(1, 1, n, i); cout << vec[t-1] << ln; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); // ll TT; cin >> TT; // while (TT--) {solve();} solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...