Submission #713448

#	Time	Username	Problem	Language	Result	Execution time	Memory
713448		hpesoj	Election (BOI18_election)	C++17	0 / 100	3 ms	856 KiB

election

#include <bits/stdc++.h>
#define int long long
#define pi pair <int, int>
#define ppi pair <pi, int>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << '\n'
#define debug2(x, y) cout << #x << ": " << x << ' ' << #y << ": " << y << '\n'
#define debug3(x, y, z) cout << #x << ": " << x << ' ' << #y << ": " << y << ' ' << #z << ": " << z << '\n'
using namespace std;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
const int inf = 1000000000;

int n, q, votes[500005], pref[500005], suff[500005];
struct node{
	int s, e, m = (s+e)>>1, val = 0;
	node *l, *r;
	node(int _s, int _e): s(_s), e(_e){
		if(s != e) l = new node(s, m), r = new node(m+1, e);
	}
	void up(int x, int v){
		if(x == s and x == e) val += v;
		else{
			if(x <= m) l->up(x, v);
			else r->up(x, v);
			val = min(l->val, r->val);
		}
	}
	int qry(int x, int y){
		if(x == s and y == e) return val;
		else if(y <= m) return l->qry(x, y);
		else if(x > m) return r->qry(x, y);
		else return min(l->qry(x, m), r->qry(m+1, y));
	}
} *PREF, *SUFF;
signed main(){
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	PREF = new node(1, n), SUFF = new node(1, n);
	for(int i = 1; i <= n; i++){
		char x; cin >> x;
		if(x == 'C') votes[i] = 1;
		else votes[i] = -1;
		pref[i] = pref[i-1] + votes[i];
		PREF->up(i, pref[i]);
	}
	for(int i = n; i >= 1; i--) suff[i] = suff[i+1] + votes[i], SUFF->up(i, suff[i]);
	cin >> q;
	while(q--){
		int l, r; cin >> l >> r;
		int a = PREF->qry(l, r) - pref[l-1], b = SUFF->qry(l, r) - suff[r+1];
		a = -a, b = -b;
		int ans = max(0ll, max(a, b));
		cout << ans << '\n';
	}
}

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