Submission #1264790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264790		duyanhchupapi	Election (BOI18_election)	C++20	100 / 100	379 ms	20292 KiB

election

#include <bits/stdc++.h>
using namespace std; const int N = 500005;
int n, q;
char c[N];
struct node{
	int pre,suf,sum,ans;
	node operator + (node b) {
		node res;
		res.sum = sum + b.sum;
		res.pre = max(pre, sum + b.pre);
		res.suf = max(b.suf, b.sum + suf);
		res.ans = max({b.ans + sum, b.sum + ans, pre + b.suf});
		return res;
	}
} seg[4*N];
void build(int x,int l,int r) {
	if(l == r) {
		if(c[l] == 'T') seg[x] = {1,1,1,1};
		else seg[x] = {0,0,-1,0};
		return;
	}
	int mid = (l+r)/2;
	build(2*x,l,mid);
	build(2*x+1,mid+1,r);
	seg[x] = seg[2*x] + seg[2*x+1];
}
node query(int x,int l,int r,int i,int j) {
	if(l > j || r < i) return {0,0,0,0};
	if(l >= i && r <= j) return seg[x];
	int mid = (l+r)/2;
	return query(2*x,l,mid,i,j) + query(2*x+1,mid+1,r,i,j);
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i=1;i<=n;++i) cin >> c[i];
	build(1,1,n);
	cin >> q;
	while(q--) {
		int l,r;cin >> l >> r;
		cout << query(1,1,n,l,r).ans << '\n';
	}
	return 0;
}

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