#include<bits/stdc++.h>
#include<vector>
using namespace std;
#define int long long
#define pb push_back
#define Good_Bye_amano_hina cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
typedef long long ll;
typedef unsigned long long ull;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn=1000005;
ll t,n,cnt,x,m,a[maxn],b[4*maxn],bb[4*maxn],ans,pos,l,r,y,tag[4*maxn],mn,k,mod=1000000007,pre[500005],suf[500005],max1,max2;
string s;
vector<int> v[30];
ll fpow(ll x,ll y)
{
if(y==0)
{
return 1%mod;
}
ll a=x%mod;
ll a2=1%mod;
while(y>1)
{
if(y%2)
{
a2*=a;
a2%=mod;
}
a*=a;
a%=mod;
y/=2;
}
return (a*a2)%mod;
}
void build(ll l,ll r,ll v)
{
if(l==r)
{
b[v]=pre[l];
return;
}
ll mid=(l+r)/2;
build(l,mid,2*v+1);
build(mid+1,r,2*v+2);
b[v]=min(b[2*v+1],b[2*v+2]);
}
ll qu(ll l, ll r, ll v, ll l2, ll r2)
{
if(l==l2&&r==r2)
{
return b[v];
}
// push
ll mid=(l+r)/2;
/*b[2*v+1]+=(mid-l+1)*tag[v];
b[2*v+2]+=(r-mid)*tag[v];
tag[2*v+1]+=tag[v];
tag[2*v+2]+=tag[v];
tag[v]=0;*/
if(mid>=r2)
{
return qu(l,mid,2*v+1,l2,r2);
}
else if(mid+1<=l2)
{
return qu(mid+1,r,2*v+2,l2,r2);
}
else
{
return min(qu(l,mid,2*v+1,l2,mid),qu(mid+1,r,2*v+2,mid+1,r2));
}
}
void build2(ll l,ll r,ll v)
{
if(l==r)
{
bb[v]=suf[l];
return;
}
ll mid=(l+r)/2;
build2(l,mid,2*v+1);
build2(mid+1,r,2*v+2);
bb[v]=min(bb[2*v+1],bb[2*v+2]);
}
ll qu2(ll l, ll r, ll v, ll l2, ll r2)
{
if(l==l2&&r==r2)
{
return bb[v];
}
// push
ll mid=(l+r)/2;
/*b[2*v+1]+=(mid-l+1)*tag[v];
b[2*v+2]+=(r-mid)*tag[v];
tag[2*v+1]+=tag[v];
tag[2*v+2]+=tag[v];
tag[v]=0;*/
if(mid>=r2)
{
return qu2(l,mid,2*v+1,l2,r2);
}
else if(mid+1<=l2)
{
return qu2(mid+1,r,2*v+2,l2,r2);
}
else
{
return min(qu2(l,mid,2*v+1,l2,mid),qu2(mid+1,r,2*v+2,mid+1,r2));
}
}
/*void modify(ll l, ll r, ll v, ll l2, ll r2, ll m)
{
if(l==l2&&r==r2)
{
//tag[v]+=m;
b[v]+=(r-l+1)*m;
return;
}
ll mid=(l+r)/2;
// push
b[2*v+1]+=(mid-l+1)*tag[v];
b[2*v+2]+=(r-mid)*tag[v];
tag[2*v+1]+=tag[v];
tag[2*v+2]+=tag[v];
tag[v]=0;
if(mid>=r2)
{
modify(l,mid,2*v+1,l2,r2,m);
}
else if(mid+1<=l2)
{
modify(mid+1,r,2*v+2,l2,r2,m);
}
else
{
modify(l,mid,2*v+1,l2,mid,m);
modify(mid+1,r,2*v+2,mid+1,r2,m);
}
b[v]=b[2*v+1]+b[2*v+2];
}*/
signed main()
{
//freopen("output.txt", "r", stdin);
Good_Bye_amano_hina
// memorize a pair
//cout<<fixed<<setprecision(20);
cin>>n;
cin>>s;
pre[0]=0;
for(int i=0;i<n;i++)
{
if(s[i]=='C')
{
pre[i+1]=pre[i]+1;
}
else
{
pre[i+1]=pre[i]-1;
}
}
suf[n+1]=0;
for(int i=n-1;i>=0;i--)
{
if(s[i]=='C')
{
suf[i+1]=suf[i+2]+1;
}
else
{
suf[i+1]=suf[i+2]-1;
}
}
build(1,n,0);
build2(1,n,0);
cin>>t;
while(t--)
{
cin>>l>>r;
x=qu(1,n,0,l,r);
max1=max(0LL,pre[l-1]-x);
x=qu2(1,n,0,l,r);
max2=max(0LL,suf[r+1]-x);
cout<<max(max1,max2)<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
