Submission #480759

#TimeUsernameProblemLanguageResultExecution timeMemory
480759tranxuanbachmedians (balkan11_medians)C++17
100 / 100
140 ms20908 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define endl '\n' #define fi first #define se second #define For(i, l, r) for (int i = l; i < r; i++) #define ForE(i, l, r) for (int i = l; i <= r; i++) #define FordE(i, l, r) for (int i = l; i >= r; i--) #define Fora(v, a) for (auto v: a) #define bend(a) a.begin(), a.end() #define isz(a) ((signed)a.size()) using ll = long long; using ld = long double; using pii = pair <int, int>; using vi = vector <int>; using vpii = vector <pii>; using vvi = vector <vi>; const int N = 2e5 + 5; struct lazy_segment_tree{ int seg[4 * N], lazy[4 * N]; void build(int id, int l, int r){ if (l == r){ seg[id] = 0; lazy[id] = 0; return; } int mid = (l + r) >> 1; build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r); seg[id] = 0; lazy[id] = 0; } void down(int id){ if (lazy[id] == 0){ return; } seg[id * 2] = max(seg[id * 2], lazy[id]); lazy[id * 2] = max(lazy[id * 2], lazy[id]); seg[id * 2 + 1] = max(seg[id * 2 + 1], lazy[id]); lazy[id * 2 + 1] = max(lazy[id * 2 + 1], lazy[id]); lazy[id] = 0; } void update(int id, int l, int r, int u, int v, int val){ if (v < l or r < u){ return; } if (u <= l and r <= v){ seg[id] = max(seg[id], val); lazy[id] = max(lazy[id], val); return; } down(id); int mid = (l + r) >> 1; update(id * 2, l, mid, u, v, val); update(id * 2 + 1, mid + 1, r, u, v, val); seg[id] = max(seg[id * 2], seg[id * 2 + 1]); } int get(int id, int l, int r, int u, int v){ if (v < l or r < u){ return 0; } if (u <= l and r <= v){ return seg[id]; } down(id); int mid = (l + r) >> 1; return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v)); } } seg; int n, m; int a[N]; int ans[N]; vi vpos[N]; set <int> stt; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("KEK.inp", "r", stdin); // freopen("KEK.out", "w", stdout); cin >> n; ForE(i, 1, n){ cin >> a[i]; } m = 2 * n - 1; seg.build(1, 1, m); ForE(i, 2, n){ if (a[i] > a[i - 1]){ seg.update(1, 1, m, a[i - 1] + 1, a[i] - 1, i); } else if (a[i] < a[i - 1]){ seg.update(1, 1, m, a[i] + 1, a[i - 1] - 1, i); } } ForE(i, 1, m){ vpos[seg.get(1, 1, m, i, i)].emplace_back(i); } Fora(pos, vpos[0]){ stt.insert(pos); } ans[1] = a[1]; stt.erase(ans[1]); ForE(i, 2, n){ if (a[i] > a[i - 1]){ ans[2 * i - 2] = *stt.upper_bound(a[i - 1]); stt.erase(ans[2 * i - 2]); ans[2 * i - 1] = *stt.upper_bound(a[i - 1]); stt.erase(ans[2 * i - 1]); } else if (a[i] < a[i - 1]){ ans[2 * i - 2] = *(--stt.lower_bound(a[i - 1])); stt.erase(ans[2 * i - 2]); ans[2 * i - 1] = *(--stt.lower_bound(a[i - 1])); stt.erase(ans[2 * i - 1]); } else{ ans[2 * i - 2] = *stt.upper_bound(a[i - 1]); stt.erase(ans[2 * i - 2]); ans[2 * i - 1] = *(--stt.lower_bound(a[i - 1])); stt.erase(ans[2 * i - 1]); } Fora(pos, vpos[i]){ stt.insert(pos); } } ForE(i, 1, m){ cout << ans[i] << ' '; } cout << endl; } /* ==================================================+ INPUT: | --------------------------------------------------| --------------------------------------------------| ==================================================+ OUTPUT: | --------------------------------------------------| --------------------------------------------------| ==================================================+ */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...