Submission #668893

#	Time	Username	Problem	Language	Result	Execution time	Memory
668893		Onur_Ilgaz	Election (BOI18_election)	C++17	0 / 100	1 ms	1040 KiB

election

#include "bits/stdc++.h"
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define int long long
#define spc " "
#define nd "\n"
#define all(a) a.begin(),a.end()
#define nm 500005
#define rep(b,a) for(int b=0;b<a;b++)
#define REP(b,a) for(int b=1;b<=a;b++)
#define inf 1e18
using namespace std;
int pre[nm], sparse[nm][20];
int pre2[nm], sparse2[nm][20];


int mini(int a, int b){
	int ans=inf;
	for(int i=18; i>0; i--){
		while(a+(1<<i)-1 <= b){
			ans=min(ans, sparse[a-1][i]);
			a=a+(1<<i)-1;
		}
	}
	return ans;
}

int mini2(int a, int b){
	int ans=inf;
	for(int i=18; i>0; i--){
		while(a+(1<<i)-1 <= b){
			ans=min(ans, sparse2[a-1][i]);
			a=a+(1<<i)-1;
		}
	}
	return ans;
}

int32_t main(){
	fast
	#ifdef Local
    freopen("in","r",stdin);
    freopen("out","w",stdout);
    #endif
    int n, prev=0;
    string s;
    cin>>n;
    cin>>s;
    rep(i, n){
    	if(s[i]=='C'){
    		pre[i]=prev+1;
    	}
    	else{
    		pre[i]=prev-1;
    	}
    	prev=pre[i];
    }
    prev=0;
    for(int i=n-1; i>=0; i--){
    	if(s[i]=='C'){
    		pre2[i]=prev+1;
    	}
    	else{
    		pre2[i]=prev-1;
    	}
    	prev=pre2[i];
    }
    rep(i, n){
    	sparse[i][0]=pre[i];
    }
    rep(i, n){
    	sparse2[i][0]=pre2[i];
    }
    for(int i=1; (1<<i)<n; i++){
    	for(int j=0; j<n; j++){
    		sparse[j][i]=min(sparse[j][i-1], sparse[j+(1<<i)-1][i-1]);
    	}
    }
    for(int i=1; (1<<i)<n; i++){
    	for(int j=0; j<n; j++){
    		sparse2[j][i]=min(sparse2[j][i-1], sparse2[j+(1<<i)-1][i-1]);
    	}
    }
    int q;
    cin>>q;
    while(q--){
    	int a, b;
    	cin>>a>>b;
    	int hm=max(0ll, a-2);
    	int k=mini(a, b)-pre[hm], l=mini2(a, b)-pre2[b];
    	if(k > 0 and l > 0){
    		cout<<0<<nd;
    	}
    	else{
    		cout<<max(-k, -l)<<nd;
    	}
    }
	#ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
	return 0;
}

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