Submission #69512

# Submission time Handle Problem Language Result Execution time Memory
69512 2018-08-21T06:57:41 Z khohko Election (BOI18_election) C++17
0 / 100
50 ms 47316 KB
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define MAX ((ll)(1e9+100))
#define MX ((ll)(1e6+100))
#define ARRS ((ll)(2e6+100))
#define HS ((ll)(233))
#define MOD ((ll)(1e9+7))
#define EP ((double)(1e-9))
#define LG 21
#define mul(a,b) a=((a)*(b))%MOD
using namespace std;

ll n;
ll m,k;
vector<ll> v[ARRS];
ll f[ARRS];
ll a[ARRS];
ll sm[ARRS];
ll ct[ARRS];

ll sum(ll l,ll r){
	return sm[r]-sm[l-1];
}

int main(){
	#ifdef KHOKHO
		freopen("in.in","r",stdin);
		freopen("out.out","w",stdout);
	#endif // KHOKHO
	ios::sync_with_stdio(0);
	ll n;
	string s;
	cin>>n>>s;
	for(int i=1; i<=n; i++){
		if(s[i-1]=='C')a[i]=1;
		else a[i]=-1;
	}
	for(int i=1; i<=n; i++)
		sm[i]=sm[i-1]+a[i];
	for(int i=1; i<=n; i++)
		ct[i]=ct[i-1]+(a[i]==-1);
	ll q,l,r;
	cin>>q;
	while(q--){
		cin>>l>>r;
		ll mx=l;
		ll mn=r;
		ll ma=0,mb=0;
		for(ll i=l; i<=r; i++){
			if(sum(l,i)<0)mx=max(mx,i);
			if(sum(i,r)<0)mn=min(mn,i);
			ma=max(ma,-sum(l,i));
			mb=max(mb,-sum(i,r));
		}

	//	cout<<ma<<" "<<mb<<endl;
		if(mx>mn){
			ma=mb=0;
			for(int i=l; i<=r; i++){
				if(i<mn)
					ma=max(ma,-sum(l,i));
				else if(i>mx)
					mb=max(mb,-sum(i,r));
			}
			ll pas=0;
			for(int i=l; i<=r; i++){
				if(mn<=i&&i<=mx)
					pas=max(pas,max(-sum(l,i)-ma,-sum(i,r)-mb));
			}
			cout<<ma+mb+pas<<endl;
		}
		else cout<<ma+mb<<endl;

	}


}
# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 47316 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 47316 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 47316 KB Output isn't correct
2 Halted 0 ms 0 KB -