Submission #902641

#TimeUsernameProblemLanguageResultExecution timeMemory
902641tvladm2009Stone Arranging 2 (JOI23_ho_t1)C++17
60 / 100
2054 ms35300 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define mp(a, b) make_pair(a, b) const int N = 2e5 + 7; pair<int, int> tree[4 * N]; pair<int, int> lazy[4 * N]; void push(int v, int tl, int tr) { if (tl < tr) { lazy[2 * v] = max(lazy[2 * v], lazy[v]); lazy[2 * v + 1] = max(lazy[2 * v + 1], lazy[v]); } tree[v] = max(tree[v], lazy[v]); lazy[v] = mp(0, 0); } void update(int v, int tl, int tr, int l, int r, pair<int, int> c) { push(v, tl, tr); if (l <= tl && tr <= r) { lazy[v] = max(lazy[v], c); push(v, tl, tr); return; } int tm = (tl + tr) / 2; if (l <= tm) update(2 * v, tl, tm, l, min(r, tm), c); if (tm + 1 <= r) update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, c); push(2 * v, tl, tm); push(2 * v + 1, tm + 1, tr); tree[v] = max(tree[2 * v], tree[2 * v + 1]); } pair<int, int> query(int v, int tl, int tr, int l, int r) { push(v, tl, tr); if (l <= tl && tr <= r) { return tree[v]; } int tm = (tl + tr) / 2; if (l <= tm && r <= tm) { return query(2 * v, tl, tm, l, r); } else if (tm + 1 <= l && tm + 1 <= r) { return query(2 * v + 1, tm + 1, tr, l, r); } else { return max(query(2 * v, tl, tm, l, tm), query(2 * v + 1, tm + 1, tr, tm + 1, r)); } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n + 1); for (int i = 1; i <= n; ++i) cin >> a[i]; vector<int> v; map<int, vector<int>> pos; for (int i = 1; i <= n; ++i) { if (pos[a[i]].size() == 0) { pos[a[i]].push_back(i); update(1, 1, n, i, i, mp(i, a[i])); continue; } int l = pos[a[i]].back(); update(1, 1, n, l, i, mp(i, a[i])); for (int j = i - 1; j >= l; --j) if (!pos[a[j]].empty() && pos[a[j]].back() == j) pos[a[j]].pop_back(); pos[a[i]].push_back(i); } for (int i = 1; i <= n; ++i) cout << query(1, 1, n, i, i).second << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...