This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define f first
#define s second
int sum[500005][2],n,q;
int mni[4*500005][2];
string s;
int build(int ni,int ns,int ne,bool d)
{
if(ns==ne)
{
return mni[ni][d]=ns;
}
int mid=ns+(ne-ns)/2;
int x=build(ni*2+1,ns,mid,d);
int y=build(ni*2+2,mid+1,ne,d);
if(sum[x][d]>=sum[y][d])
mni[ni][d]=x;
else
mni[ni][d]=y;
return mni[ni][d];
}
int query(int ni,int ns,int ne,int nl,int nr,bool d)
{
if(nr<ns||ne<nl)
return n;
if(nl<=ns&&ne<=nr)
return mni[ni][d];
int mid=ns+(ne-ns)/2;
int x=query(ni*2+1,ns,mid,nl,nr,d);
int y=query(ni*2+2,mid+1,ne,nl,nr,d);
if(sum[x][d]>=sum[y][d])
return x;
return y;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin>>n;
cin>>s;
for(int i=0;i<n;i++)
{
if(!i)
{
sum[i][0]=2*(s[i]=='T')-1;
}
else
sum[i][0]=2*(s[i]=='T')-1+sum[i-1][0];
}
for(int i=n-1;i>=0;i--)
{
if(i==n-1)
{
sum[i][1]=2*(s[i]=='T')-1;
}
else
sum[i][1]=2*(s[i]=='T')-1+sum[i+1][1];
}
sum[n][0]=sum[n][1]=-1e9;
build(0,0,n-1,0);
build(0,0,n-1,1);
cin>>q;
int l,r;
while(q--)
{
cin>>l>>r;
l--,r--;
int pr=query(0,0,n-1,l,r,0),sf=query(0,0,n-1,l,r,1);
int ans=max(sum[pr][0]-(l?sum[l-1][0]:0),sum[sf][1]-(r==n-1?0:sum[r+1][1]));
ans=max(ans,0ll);
cout<<ans<<"\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |