Submission #1017791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017791		KN200711	Election (BOI18_election)	C++14	0 / 100	2 ms	600 KiB

election

# include <bits/stdc++.h>
# define ll long long
# define ld double
# define fi first
# define se second
# define pll pair<ll, ll>
using namespace std;

int val[500001];
int seg[2][2000020];

void build(int lf, int rg, int nd) {
	if(lf == rg) {
		seg[0][nd] = seg[1][nd] = val[lf];
	} else {
		int mid = (lf + rg) / 2;
		build(lf, mid, 2*nd+1);
		build(mid+1, rg, 2*nd+2);
		seg[0][nd] = max(seg[0][2*nd + 1], seg[0][2 * nd + 2]);
		seg[1][nd] = min(seg[1][2*nd+1], seg[1][2 * nd + 2]);
	}
}

int qry(int lf, int rg, int nd, int clf, int crg, int ty) {
	if(lf > crg || clf > rg) {
		if(ty == 0) return -1e9;
		return 1e9;
	} else if(clf <= lf && rg <= crg) return seg[ty][nd];
	int mid = (lf + rg) / 2;
	if(ty == 0) return max(qry(lf, mid, 2*nd+1, clf, crg, ty), qry(mid+1, rg, 2*nd+2, clf, crg, ty));
	else return min(qry(lf, mid, 2*nd+1, clf, crg, ty), qry(mid+1, rg, 2*nd+2, clf, crg, ty));
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int N;
	cin>>N;
	
	string S;
	cin>>S;
	
	for(int i=1;i<=N;i++) {
		if(S[i - 1] == 'C') val[i] = val[i - 1] + 1;
		else val[i] = val[i - 1] - 1;
	}
	
	build(0, N, 0);
	int Q;
	cin>>Q;
	while(Q--) {
		int L, R;
		cin>>L>>R;
		
		int mx = qry(0, N, 0, L, R, 0);
		int mn = qry(0, N, 0, L, R, 1);
		int fr = val[L - 1];
		int lst = val[R];
		
		cout<<max(mx - lst, -(mn - fr))<<"\n";
	}
	return 0;
}

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