oj.uz

Submission #1085180

# Submission time Handle Problem Language Result Execution time Memory
1085180 2024-09-07T16:38:55 Z elotelo966 Election (BOI18_election) C++17
28 / 100
 2 ms 1368 KB 
#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 10005
#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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Runtime error 2 ms 1368 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Runtime error 2 ms 1368 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -