#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?0:sum[l-1][0]),sum[sf][1]-(r==n-1?0:sum[r+1][1]));
cout<<ans<<"\n";
}
}
Compilation message
election.cpp: In function 'int main()':
election.cpp:71:44: warning: array subscript -1 is below array bounds of 'long long int [500005][2]' [-Warray-bounds]
71 | int ans=max(sum[pr][0]-(l?0:sum[l-1][0]),sum[sf][1]-(r==n-1?0:sum[r+1][1]));
| ~~~~~~~^
election.cpp:7:5: note: while referencing 'sum'
7 | int sum[500005][2],n,q;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
