Submission #1267225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267225		akmuhammet_s	Election (BOI18_election)	C++20	0 / 100	1 ms	320 KiB

election

#include "bits/stdc++.h"
using namespace std;
#define mod 998244353
#define ll long long
#define N 24
#define maxn 200005

void solve(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	int sq=sqrt(n);
	int p[n+5],pg[n+5],ss[n+5],ps[n+5];
	int cur=0,mn=1e9;
	for(int i=0; i<s.size(); i++){
		if(s[i]=='C') cur++;
		else cur--;
		p[i]=cur;
		mn=min(mn,cur);
		if(i%sq==(sq-1)){
			pg[i/sq]=mn;
			mn=1e9;
		}
	}
	cur=0;
	for(int i=0; i<s.size(); i++){
		if(s[s.size()-1-i]=='C') cur++;
		else cur--;
		ss[i]=cur;
		mn=min(mn,cur);
		if(i%sq==(sq-1)){
			ps[i/sq]=mn;
			mn=1e9;
		}
	}
	int q;
	cin>>q;
	while(q--){
		int l,r;
		cin>>l>>r;
		int x=1e9;
		for(int i=l-1; i<r; i++){
			if(i%sq==0 and (i+sq)<=r){
				x=min(x,pg[i/sq]);
				i=i+sq-1;
			}else{
				x=min(x,p[i]);
			}
		}
		if(l>1){
			x-=ss[l-2];
		}
		int ans=x;
		x=1e9;
		int yl=n-r,rr=n-l;
		for(int i=yl; i<=rr; i++){
			if(i%sq==0 and (i+sq)<=r){
				x=min(x,ps[i/sq]);
				i=i+sq-1;
			}else{
				x=min(x,ss[i]);
			}
		}
		if(r<n){
			x-=ss[n-r-1];
		}
		ans=min(ans,x);
		cout<<abs(ans)<<'\n';
	}
}
 
int main(){
	// freopen("in.txt","w",stdout);
	// freopen("out.txt","r",stdin);
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll t=1;
	// cin>>t;
	while(t--) solve();
}

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