Submission #611468

#	Time	Username	Problem	Language	Result	Execution time	Memory
611468		juggernaut	Election (BOI18_election)	C++14	0 / 100	4 ms	596 KiB

election

#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
    #define printl(args...) printf(args)
#else
    #define printl(args...) 0
#endif
int n,q;
int pref[500005];
int mn[500005][20];
int suff[500005];
int mn2[500005][20];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	string s;
	cin>>s;
	for(int i=1;i<=n;i++){
		pref[i]=pref[i-1];
		if(s[i-1]=='C')pref[i]++;
		else pref[i]--;
		mn[i][0]=pref[i];
	}
	for(int i=n;i;i--){
		suff[i]=suff[i+1];
		if(s[i-1]=='C')suff[i]++;
		else suff[i]--;
		mn2[i][0]=suff[i];
	}
	for(int j=1;j<20;j++)
	for(int i=1;i+(1<<j)-1<=n;i++){
		mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
		mn2[i][j]=min(mn2[i][j-1],mn2[i+(1<<(j-1))][j-1]);
	}
	int q;
	cin>>q;
	while(q--){
		int l,r;
		cin>>l>>r;
		int len=__lg(r-l+1);
		int m=min(min(mn[l][len],mn[r-(1<<len)+1][len])-pref[l-1],min(mn2[l][len],mn2[r-(1<<len)+1][len])-suff[r+1]);
		umin(m,0);
		cout<<-m<<endl;
	}
}

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