Submission #318442

#	Time	Username	Problem	Language	Result	Execution time	Memory
318442		kapsel	Election (BOI18_election)	C++17	0 / 100	2 ms	364 KiB

election

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned LL
#define LD long double
#define debug(x) cerr << #x << " " << x << endl;

const int INF = 1e9 + 2137;

template<class T> struct Seg {
	T ID = INF; T comb(T a, T b) { return min(a, b); }
	int n; vector<T> seg;
	void init(int _n) { n = _n; seg.assign(2*n, ID); }
	void pull(int p) { seg[p] = comb(seg[2*p], seg[2*p+1]); }
	void upd(int p, T val) { seg[p+=n] = val; for(p/=2; p; p/=2) pull(p); }
	T query(int l, int r) {
		T ra = ID, rb = ID;
		for(l+=n, r+=n+1; l < r; l/=2, r/=2) {
			if(l&1) ra = comb(ra, seg[l++]);
			if(r&1) rb = comb(seg[--r], rb);
		}
		return comb(ra, rb);
	}
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	string S;
	cin>>S;
	int p[n];
	int s[n];
	Seg<int> pref, suf;
	pref.init(n);
	suf.init(n);
	p[0] = (S[0] == 'C' ? 1 : -1);
	s[n-1] = (S[n-1] == 'C' ? 1 : -1);
	pref.upd(0, p[0]);
	suf.upd(n-1, s[n-1]);
	for(int i=1; i<n; i++) {
		p[i] = p[i-1] + (S[i] == 'C' ? 1 : -1);
		pref.upd(i, p[i]);
	}
	for(int i=n-2; i>=0; i--) {
		s[i] = s[i+1] + (S[i] == 'C' ? 1 : -1);
		suf.upd(i, s[i]);
	}
	int q;
	cin>>q;
	while(q--) {
		int l, r;
		cin>>l>>r;
		int mp = pref.query(l-1, r-1);
		int ms = suf.query(l-1, r-1);
		//cerr<<mp<<" - "<<ms<<"\n";
		if(l != 1)
			mp -= p[l-2];
		if(r != n)
			ms -= p[r];
		int ans = min(0, min(mp, ms));
		cout<<abs(ans)<<"\n";
	}
}

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