Submission #582309

#TimeUsernameProblemLanguageResultExecution timeMemory
582309Tam_theguideElection (BOI18_election)C++14
100 / 100
613 ms27396 KiB
#include <bits/stdc++.h> using namespace std; int n, q; struct node{ int p; int s; int t; int a; }; node seg[2310000]; node combine(node x, node y){ node re; re.p = max(x.p, x.t + y.p); re.s = max(y.s, y.t + x.s); re.t = x.t + y.t; re.a = max(max(x.a + y.t, y.a + x.t), x.p + y.s); return re; } void update(int root, int tl, int tr, int pos, int val){ if (tl == tr){ seg[root].p = max(seg[root].p, val); seg[root].s = max(seg[root].s, val); //seg[root].p = val; seg[root].s = val; seg[root].t += val; seg[root].a = ((val == -1) ? 0 : 1); return; } int tm = (tl + tr) / 2; if (pos <= tm) update(2 * root, tl, tm, pos, val); else update(2 * root + 1, tm + 1, tr, pos, val); seg[root] = combine(seg[2 * root], seg[2 * root + 1]); } node query(int root, int tl, int tr, int l, int r){ if (tl > r || tr < l) return {0, 0, 0, 0}; if (tl >= l && tr <= r) return seg[root]; int tm = (tl + tr) / 2; return combine(query(2 * root, tl, tm, l, r), query(2 * root + 1, tm + 1, tr, l, r)); } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1;i <= n;i ++){ char x; cin >> x; update(1, 1, n, i, ((x == 'C') ? -1 : 1)); } cin >> q; while (q--){ int l, r; cin >> l >> r; cout << query(1, 1, n, l, r).a << '\n'; } } /* 3 TCT 3 1 1 2 2 1 2 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...