Submission #359698

#	Time	Username	Problem	Language	Result	Execution time	Memory
359698		vkgainz	Election (BOI18_election)	C++17	100 / 100	765 ms	35284 KiB

election

#include <bits/stdc++.h>
using namespace std; const int MX = 5e5 + 5; struct node { int sum, ans, mn, mx; node() { sum = 0, ans = 0, mn = 0, mx = 0; } node(int a, int b, int c, int d): sum(a), ans(b), mn(c), mx(d) { } } seg[4 * MX]; node comb(node &a, node &b) { node ret; ret.sum = a.sum+b.sum; ret.mn = min(a.mn, b.mn + a.sum); ret.mx = max(a.mx, b.mx + a.sum); ret.ans = max({a.ans - b.sum, b.ans-a.sum, b.mx + a.sum - a.mn - ret.sum}); return ret; } int sz = 1; void build(string &s, int n, int x=0, int lx=0, int rx=sz) { if(rx-lx==1) { if(lx<n) { if(s[lx]=='C') seg[x] = node(1, -1, 0, 1); else seg[x] = node(-1, 1, -1, 0); } else seg[x] = node(); return; } int m = (lx+rx)/2; build(s, n, 2*x+1, lx, m), build(s, n, 2*x+2, m, rx); seg[x] = comb(seg[2*x+1], seg[2*x+2]); } node query(int l, int r,int x=0, int lx=0, int rx=sz) { if(lx>=r || rx<=l) return node(); if(lx>=l && rx<=r) return seg[x]; int m = (lx+rx)/2; node a = query(l, r, 2*x+1, lx, m), b = query(l, r, 2*x+2, m, rx); return comb(a, b); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; while(sz<n) sz*=2; string s; cin >> s; build(s, n); int q; cin >> q; while(q--) { int l, r; cin >> l >> r; --l, --r; node x = query(l, r+1); cout << max(0, x.ans) << "\n"; } }

• Subtask 1: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18