Submission #108774

#TimeUsernameProblemLanguageResultExecution timeMemory
108774bibabasmedians (balkan11_medians)C++14
25 / 100
201 ms12920 KiB
#ifdef LOCAL #define _GLIBCXX_DEBUG #endif #include <bits/stdc++.h> #define ll long long #define vi vector<int> #define vvi vector<vi> #define all(x) x.begin(), x.end() #define pb push_back #define mp make_pair int INF = (int)2e9; using namespace std; template <class T> istream& operator >>(istream &in, vector<T> &arr) { for (T &cnt : arr) { in >> cnt; } return in; }; pair<int, int> t_left[(int)8e5], t_right[(int)8e5]; int t_add[(int)8e5]; void push(int v, int tl, int tr){ t_left[v].first += t_add[v]; t_right[v].first += t_add[v]; if (tl != tr){ t_left[2 * v].first += t_add[v]; t_left[2 * v + 1].first += t_add[v]; t_right[2 * v].first += t_add[v]; t_right[2 * v + 1].first += t_add[v]; } t_add[v] = 0; } void update(int v, int tl, int tr, int l, int r, int val){ push(v, tl, tr); if (l > r) return; if (tl > r || l > tr) return; if (l <= tl && tr <= r){ t_add[v] += val; push(v, tl, tr); return; } int tm = (tl + tr) / 2; update(2 * v, tl, tm, l, r, val); update(2 * v + 1, tm + 1, tr, l, r, val); if (t_left[2 * v].first >= t_left[2 * v + 1].first) t_left[v] = t_left[2 * v + 1]; else t_left[v] = t_left[2 * v]; t_right[v] = min(t_right[2 * v], t_right[2 * v + 1]); } pair<int, int> query_left(int v, int tl, int tr, int l, int r){ push(v, tl, tr); if (l <= tl && tr <= r) return t_left[v]; if (tl > r || l > tr) return make_pair(INF, -1); int tm = (tl + tr) / 2; auto a = query_left(2 * v, tl, tm, l, r), b = query_left(2 * v + 1, tm + 1, tr, l, r); if (a.first >= b.first) return b; else return a; } pair<int, int> query_right(int v, int tl, int tr, int l, int r){ push(v, tl, tr); if (l <= tl && tr <= r) return t_right[v]; if (tl > r || l > tr) return make_pair(INF, -1); int tm = (tl + tr) / 2; auto a = query_right(2 * v, tl, tm, l, r), b = query_right(2 * v + 1, tm + 1, tr, l, r); return min(a, b); } void build(int v, int tl, int tr){ if (tl == tr) { t_left[v] = mp(0, tl); t_right[v] = mp(0, tl); return; } int tm = (tl + tr) / 2; build(2 * v, tl, tm); build(2 * v + 1, tm + 1, tr); t_left[v] = mp(0, tr); t_right[v] = mp(0, tl); } void solve() { int n; cin >> n; vi b(n); cin >> b; build(1, 1, 2 * n - 1); for (int i = 1; i < n; ++i){ update(1, 1, 2 * n - 1, min(b[i - 1], b[i]) + 1, max(b[i], b[i - 1]) - 1, 1); } cout << b[0] << " "; update(1, 1, 2 * n - 1, b[0], b[0], 1); for (int i = 1; i < n; ++i){ if (b[i] > b[i - 1]){ auto a = query_right(1, 1, 2 * n - 1, b[i - 1], 2 * n - 1); update(1, 1, 2 * n - 1, a.second, a.second, 1); auto c = query_right(1, 1, 2 * n - 1, b[i - 1], 2 * n - 1); update(1, 1, 2 * n - 1, c.second, c.second, 1); update(1, 1, 2 * n - 1, b[i - 1] + 1, b[i] - 1, -1); cout << a.second << " " << c.second << " "; } if (b[i] == b[i - 1]){ auto a = query_right(1, 1, 2 * n - 1, b[i - 1], 2 * n - 1); update(1, 1, 2 * n - 1, a.second, a.second, 1); auto c = query_left(1, 1, 2 * n - 1, 1, b[i - 1]); update(1, 1, 2 * n - 1, c.second, c.second, 1); update(1, 1, 2 * n - 1, b[i - 1] + 1, b[i] - 1, -1); cout << a.second << " " << c.second << " "; } if (b[i] < b[i - 1]){ auto a = query_left(1, 1, 2 * n - 1, 1, b[i - 1]); update(1, 1, 2 * n - 1, a.second, a.second, 1); auto c = query_left(1, 1, 2 * n - 1, 1, b[i - 1]); update(1, 1, 2 * n - 1, c.second, c.second, 1); update(1, 1, 2 * n - 1, b[i] + 1, b[i - 1] - 1, -1); cout << a.second << " " << c.second << " "; } } } int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #else ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #endif solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...