Submission #314665

#TimeUsernameProblemLanguageResultExecution timeMemory
314665apostoldaniel854Election (BOI18_election)C++14
100 / 100
1458 ms54692 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define pb push_back #define dbg(x) cerr << #x << " " << x << "\n" const int N = 5e5; struct SegTree { /// struct Node { int sum; int mnSuf; }; vector <Node> seg; int n; SegTree (int n) { this-> n = n; seg.resize (1 + 4 * n); } Node join (Node lNode, Node rNode) { return {lNode.sum + rNode.sum, min (rNode.mnSuf, lNode.mnSuf + rNode.sum)}; } void updatePos (int node, int lb, int rb, int pos, int val) { if (lb == rb) { seg[node] = {val, min (val, 0)}; return; } int mid = (lb + rb) / 2; if (pos <= mid) updatePos (node * 2, lb, mid, pos, val); else updatePos (node * 2 + 1, mid + 1, rb, pos, val); seg[node] = join (seg[node * 2], seg[node * 2 + 1]); } Node queryRange (int node, int lb, int rb, int qL, int qR) { if (qL <= lb && rb <= qR) return seg[node]; int mid = (lb + rb) / 2; Node ans = {0, 0}; if (qL <= mid) ans = join (ans, queryRange (node * 2, lb, mid, qL, qR)); if (qR >= mid + 1) ans = join (ans, queryRange (node * 2 + 1, mid + 1, rb, qL, qR)); return ans; } }; vector <pair <int, int>> qry[1 + N]; int val[1 + N]; int main () { int n; string votes; cin >> n >> votes; for (int i = 0; i < n; i++) val[i + 1] = votes[i] == 'C' ? 1 : -1; int q; cin >> q; for (int i = 0; i < q; i++) { int l, r; cin >> l >> r; qry[l].pb ({r, i}); } SegTree seg (n); vector <int> stk; for (int i = 1; i <= n; i++) seg.updatePos (1, 1, n, i, val[i]); vector <int> sol (q); for (int i = n; i > 0; i--) { if (val[i] == 1) { if (stk.size ()) { seg.updatePos (1, 1, n, stk.back (), -1); stk.pop_back (); } } else { seg.updatePos (1, 1, n, i, 0); stk.push_back (i); } for (pair <int, int> it : qry[i]) { int l = i; int r = it.first; int index = it.second; sol[index] = - seg.queryRange (1, 1, n, l, r).mnSuf + (upper_bound (stk.rbegin (), stk.rend (), r) - stk.rbegin ()); } } for (int x : sol) cout << x << "\n"; cout << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...