Submission #1085182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085182		elotelo966	Election (BOI18_election)	C++17	28 / 100	50 ms	10644 KiB

election

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define OYY LLONG_MAX
#define mod 998244353
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define lim 500005
#define fi first
#define se second

array<int,4> bos;

int arr[lim];

int sum[4*lim],ans[4*lim],le[4*lim],ri[4*lim];

inline void build(int node,int start,int end){
	if(start==end){
		sum[node]=le[node]=ri[node]=ans[node]=arr[start];
		ans[node]=max(ans[node],0ll);
		return ;
	}
	build(node*2,start,mid),build(node*2+1,mid+1,end);
	sum[node]=sum[node*2]+sum[node*2+1];
	le[node]=max(le[node*2],sum[node*2]+le[node*2+1]);
	ri[node]=max(ri[node*2+1],sum[node*2+1]+ri[node*2]);
	ans[node]=max({ans[node*2]+sum[node*2+1],ans[node*2+1]+sum[node*2],le[node*2]+ri[node*2+1],0ll});
}

inline array<int,4> query(int node,int start,int end,int l,int r){
	if(start>end || start>r || end<l)return bos;
	if(start>=l && end<=r){
		array<int,4> tut;
		tut[0]=sum[node];
		tut[1]=le[node];
		tut[2]=ri[node];
		tut[3]=ans[node];
		return tut;
	}
	array<int,4> tut;
	array<int,4> left=query(node*2,start,mid,l,r);
	array<int,4> right=query(node*2+1,mid+1,end,l,r);
	tut[0]=left[0]+right[0];
	tut[1]=max(left[1],left[0]+right[1]);
	tut[2]=max(right[2],right[0]+left[2]);
	tut[3]=max({left[3]+right[0],right[3]+left[0],left[1]+right[2],0ll});
	return tut;
}

inline void debug(int node,int start,int end){
	cout<<node<<" "<<start<<" "<<end<<" "<<sum[node]<<" "<<le[node]<<" "<<ri[node]<<" "<<ans[node]<<endl;
	if(start==end)return ;
	debug(node*2,start,mid),debug(node*2+1,mid+1,end);
}

int32_t main(){
	faster
	int n;cin>>n;
	string s;cin>>s;
	FOR{
		if(s[i-1]=='C')arr[i]=-1;
		else arr[i]=1;
	}
	
	build(1,1,n);
	
	//debug(1,1,n);
	
	int q;cin>>q;
	while(q--){
		int x,y;cin>>x>>y;
		array<int,4> tut=query(1,1,n,x,y);
		cout<<tut[3]<<'\n';
	}
	
	return 0;
}

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