Submission #713448

# Submission time Handle Problem Language Result Execution time Memory
713448 2023-03-22T03:37:22 Z hpesoj Election (BOI18_election) C++17
0 / 100
3 ms 856 KB
#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';
	}
}
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 856 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 856 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 856 KB Output isn't correct
2 Halted 0 ms 0 KB -