#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 |
- |
