Submission #571984

#	Time	Username	Problem	Language	Result	Execution time	Memory
571984		duytuandao21	Election (BOI18_election)	C++17	100 / 100	608 ms	28016 KiB

election

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+7;
int n,q,m,a[N]; 
string s;
struct node {
	int minimum_result;
	int sum;
	int minl;
	int minr;
};
node seg[N];
node join(node x, node y) {
	return {
		//max(l.l + r.r, max(l.s + r.a, l.a + r.s))
		max(x.minl + y.minr, max(x.sum + y.minimum_result, x.minimum_result + y.sum)), 
		x.sum + y.sum, 
		//l.s + r.s
		max(x.minl, x.sum + y.minl),
		//max(l.l, l.s + r.l)
		max(y.minr, y.sum + x.minr)
		//max(l.r + r.s, r.r))
	};
}
void build(int id,int l,int r, int pos, int val) {
	if(l > r || r < pos || l > pos) return;
	if(l == r) {
		seg[id].sum = val;
		seg[id].minl = max(seg[id].minl, val);
		seg[id].minr = max(seg[id].minr, val);
		seg[id].minimum_result = max(seg[id].minimum_result, val);
		return;
	}
	int mid = (l + r) / 2;
	build(id*2,l,mid,pos,val);
	build(id*2+1,mid+1,r,pos,val);
	seg[id] = join(seg[id*2], seg[id*2+1]);
}
node get(int id,int l,int r,int u,int v) {
	if(l > v || r < u) return {0,0,0,0};
	if(l >= u && r <= v) return seg[id];
	int mid = (l + r) / 2;
	return join(get(id*2,l,mid,u,v), get(id*2+1,mid+1,r,u,v));
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>s>>q;
	for(int i=0;i<n;i++) if(s[i] == 'C') build(1,1,n,i+1,-1); else build(1,1,n,i+1,1);
	//build(1,1,n);
	while(q--) {
		int l,r;
		cin>>l>>r;
		cout<<get(1,1,n,l,r).minimum_result<<'\n';
	}
	return 0;
}

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