제출 #1267312

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267312		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 pref[n+5],prefg[n+5];
	int cur=0,x=1e9;
	for(int i=0; i<s.size(); i++){
		if(s[i]=='C') cur++;
		else cur--;
		x=min(x,cur);
		pref[i]=cur;
		if(i%sq==(sq-1)){
			prefg[i/sq]=x;
			x=1e9;
		}
	}
	cur=0;
	x=1e9;
	int suf[n+5],sufg[n+5];
	for(int i=s.size()-1; i>=0; i--){
		if(s[i]=='C') cur++;
		else cur--;
		x=min(x,cur);
		suf[i]=cur;
		if(i%sq==0){
			sufg[i/sq]=x;
			x=1e9;
		}
	}
	int q;
	cin>>q;
	while(q--){
		int l,r;
		cin>>l>>r;
		int mn=1e9;
		for(int i=l-1; i<r; i++){
			if(i%sq==0 and i+sq<=r){
				mn=min(mn,prefg[i/sq]);
				i=i+sq-1;
				continue;
			}
			mn=min(mn,pref[i]);
		}
		if(l>1){
			mn-=pref[l-2];
		}
		int ans=mn;
		mn=1e9;
		for(int i=l-1; i<r; i++){
			if(i%sq==0 and i+sq<=r){
				mn=min(mn,sufg[i/sq]);
				i=i+sq-1;
				continue;
			}
			mn=min(mn,suf[i]);
		}
		if(r<n){
			mn-=suf[r];
		}
		ans=min(ans,mn);
		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