#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN =1e5+5;
struct node{
int sum,suffsum;
node(int sum = 0,int suffsum = 0){
this->sum = sum;
this->suffsum = suffsum;
}
node join(node &other){
return node(sum+other.sum,min(other.suffsum,other.sum+suffsum));
}
};
node a[4*MAXN + 5];
void update(int curr,int l,int r,int pos,int val){
if(pos>r||pos<l){
return;
}
// cout<<pos<<" "<<l<<" "<<r<<endl;
if(l == r){
a[curr].sum+=val;
a[curr].suffsum+=val;
return;
}
int mid = (l+r)/2;
update(2*curr,l,mid,pos,val);
update(2*curr+1,mid+1,r,pos,val);
a[curr] = a[2*curr].join(a[2*curr+1]);
}
node query(int curr,int l, int r,int tl,int tr){
if(tl>r||tr<l){
node temp;
temp.sum = 0;
temp.suffsum = 0;
return temp;
}
if(tl<=l && r<=tr){
return a[curr];
}
int mid = (l+r)/2;
node a = query(2*curr,l,mid,tl,tr);
node b = query(2*curr+1,mid+1,r,tl,tr);
return a.join(b);
}
int n,q;
int rem[MAXN];
int len;
int holdans[MAXN];
vector<pair<int,int>> queries[MAXN];
int main(){
cin>>n;
string s;
cin>>s;
cin>>q;
s = '#' + s;
for(int i=1;i<=q;i++){
int l,r;
cin>>l>>r;
queries[l].push_back(make_pair(r,i));
}
for(int i=n;i>=1;i--){
if(s[i] == 'T'){
rem[len++] = i;
}else{
update(1,1,n,i,1);
//cout<<query(1,1,n,i,n).suffsum<<endl;
if(len){
update(1,1,n,rem[len-1],-1);
//cout<<rem[len-1]<<endl;
len--;
}
}
for(auto it:queries[i]){
//cout<<len<<" "<<it.first<<endl;
int l=0;
int r = len-1;
int ans = -1;
while(l<=r){
int mid = (l+r)/2;
if(rem[mid]<=it.first){
ans = mid;
l = mid+1;
}else{
r = mid-1;
}
}
// cout<<ans<<endl;
//cout<<len<<" "<<ans+1<<endl;
// cout<<-1*query(1,1,n,i,it.first).suffsum<<endl;
holdans[it.second] = max(0,-1*query(1,1,n,i,it.first).suffsum) + ans+1;
}
}
for(int i=1;i<=q;i++){
cout<<holdans[i]<<" ";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
5888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
5888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
5888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
