#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned LL
#define LD long double
#define debug(x) cerr << #x << " " << x << endl;
typedef pair<int, int> pi;
const int INF = 1e9 + 2137;
struct T {
int suma, minSuf;
T() {
suma = 0;
minSuf = INF;
}
T(int x) {
suma = x;
minSuf = x;
}
T(int a, int b) {
suma = a;
minSuf = b;
}
};
struct Seg {
T ID = T(0, INF);
T comb(T a, T b) {
T w;
w.suma = a.suma + b.suma;
w.minSuf = min(b.minSuf, b.suma+a.minSuf);
return w;
}
int n; vector<T> seg;
void init(int _n) { n = _n; seg.assign(2*n, ID); }
void pull(int p) { seg[p] = comb(seg[2*p], seg[2*p+1]); }
void upd(int p, int val) {
seg[p+=n] = T(val);
for(p/=2; p; p/=2) pull(p);
}
int query(int l, int r) {
T ra = ID, rb = ID;
for(l+=n, r+=n+1; l<r; l/=2, r/=2) {
if(l&1) ra = comb(ra, seg[l++]);
if(r&1) rb = comb(seg[--r], rb);
}
return comb(ra, rb).minSuf;
}
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, q;
string s;
cin>>n>>s>>q;
int a, b;
vector<pi> qry[n];
vector<int> ans(q, 0);
Seg tree;
tree.init(n);
for(int i=0; i<q; i++) {
cin>>a>>b; a--; b--;
qry[a].push_back({b, i});
}
for(int i=0; i<n; i++)
tree.upd(i, 0);
vector<int> ts;
for(int l=n-1; l>=0; l--) {
if(s[l] == 'T') ts.push_back(l);
else {
if(!ts.empty()) {
int x = ts[ts.size()-1];
tree.upd(x, -1);
ts.pop_back();
}
tree.upd(l, 1);
}
for(pi x : qry[l]) {
int r = x.first;
int i = x.second;
auto it = upper_bound(ts.begin(), ts.end(), r);
int cnt = (int) ts.size() - (ts.end() - it);
int minSuf = tree.query(l, r);
int answer = cnt + max(0, -minSuf);
ans[i] = answer;
//cerr<<"! l = "<<l<<", r = "<<r<<", minSuf = "<<minSuf<<"\n";
}
}
for(int i=0; i<q; i++)
cout<<ans[i]<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
