#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define sp << " " <<
#define int long long
#define vi vector<int>
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define ordered_set tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update>
const int inf = 2e18;
struct ST {
struct Node {
int wsuf,wpref,sm;
};
int n;
string s;
vector<Node> t;
Node merge(Node a,Node b){
Node ret;
ret.wsuf = min(b.wsuf,b.sm+a.wsuf);
ret.wpref = min(a.wpref,a.sm+b.wpref);
ret.sm = a.sm+b.sm;
return ret;
}
void build(int node,int l,int r) {
if (l == r) {
int c = s[l-1] == 'T'?-1:1;
t[node] = {c,c,c};
return;
}
int m = (l+r) >> 1;
build(2*node,l,m);
build(2*node+1,m+1,r);
t[node] = merge(t[2*node],t[2*node+1]);
return;
}
ST(int nn,string ss) {
n = nn;
s = ss;
t.resize(4*n+1);
build(1,1,n);
}
Node id = {0,0,0};
Node query(int node,int l,int r,int L,int R) {
if (l > R || r < L) return id;
if (l >= L && r <= R) return t[node];
int m = (l+r) >> 1;
return merge(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R));
}
};
void solve() {
int n;
cin >> n;
string s;
cin >> s;
ST st(n,s);
int q;
cin >> q;
while (q--) {
int l,r;
cin >> l >> r;
cout << max(0ll,-min(st.query(1,1,n,l,r).wpref,st.query(1,1,n,l,r).wsuf)) << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
