#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
//#define int long long
int n,q;
string s;
int p[200005],suff[200005],l,r;
pair <int,int> d[200005],d1[200005];
pair <int,int > mx(pair <int,int> x,pair <int,int> y){
if(x.ff==y.ff){
return make_pair(x.ff,max(x.ss,y.ss));
}else{
return min(x,y);
}
}
void buildmax(int v,int tl,int tr){
if(tl==tr){
d[v]=make_pair(suff[tl],tl);
return;
}
int tm=(tl+tr)/2;
buildmax(2*v,tl,tm);
buildmax(2*v+1,tm+1,tr);
d[v]=mx(d[2*v],d[2*v+1]);
}
pair <int,int> segmax(int v,int tl,int tr,int l,int r){
if(l>r){
return make_pair(0,0);
}
if(tl==l and tr==r){
return d[v];
}
int tm=(tl+tr)/2;
return mx(segmax(2*v,tl,tm,l,min(r,tm)),segmax(2*v+1,tm+1,tr,max(l,tm+1),r));
}
void buildmin(int v,int tl,int tr){
if(tl==tr){
d1[v]=make_pair(p[tl],tl);
return;
}
int tm=(tl+tr)/2;
buildmin(2*v,tl,tm);
buildmin(2*v+1,tm+1,tr);
d1[v]=min(d1[2*v],d1[2*v+1]);
}
pair <int,int> segmin(int v,int tl,int tr,int l,int r){
if(l>r){
return make_pair(INT_MAX,INT_MAX);
}
if(tl==l and tr==r){
// cout<<d1[v].ss<<" "<<tl<<" "<<tr<<" "<<l<<" "<<r<<endl;
return d1[v];
}
int tm=(tl+tr)/2;
// cout<<tm<<endl;
return min(segmin(2*v,tl,tm,l,min(r,tm)),segmin(2*v+1,tm+1,tr,max(l,tm+1),r));
}
int main(){
cin>>n;
cin>>s;
s=" "+s;
for(int i=1;i<=n;i++){
p[i]=p[i-1];
if(s[i]=='T'){
p[i]--;
}else{
p[i]++;
}
}
for(int i=n;i>=1;i--){
suff[i]=suff[i+1];
if(s[i]=='T'){
suff[i]--;
}else{
suff[i]++;
}
}
buildmax(1,1,n);
buildmin(1,1,n);
cin>>q;
// cout<<segmin(1,1,n,3,4).ss<<endl;
while(q--){
cin>>l>>r;
auto pos1=segmin(1,1,n,l,r);
auto pos2=segmax(1,1,n,l,r);
// cout<<pos1.ss<<" "<<pos2.ss<<endl;
if(pos1.ss<pos2.ss){
cout<<abs(pos1.ff-p[l-1])+abs((pos2.ff-suff[r+1]))<<endl;
continue;
}
auto k=segmin(1,1,n,l,pos2.ss-1);
// cout<<k.ff<<" "<<k.ss<<endl;
int fir=abs(min(0,k.ff-p[l-1]));
if(k.ss==0){
fir=0;
}
k=segmax(1,1,n,pos1.ss+1,r);
int sec=abs(min(0,(k.ff-suff[r+1])));
if(k.ss==0){
sec=0;
}
// cout<<fir<<" "<<sec<<endl;
cout<<fir+sec+max(abs(min(0,pos1.ff-p[l-1]))-fir,abs(min(0,(pos2.ff-suff[r+1])))-sec)<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
