#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef int64_t ll;
#define her cerr<<"here"<<endl;
const int N = 5e5 + 5;
struct ST{
ar<int, 2> tree[N << 2];
ar<int, 2> merge(ar<int, 2>& a, ar<int, 2>& b){
ar<int, 2> c {};
c[0] = a[0] + b[0];
c[1] = max(b[1], b[0] + a[1]);
return c;
}
void set(int i, int v, int lx = 0, int rx = N, int x = 1){
if(lx == rx){
tree[x][0] = v, tree[x][1] = max(0, v);
return;
} int m = (lx + rx) >> 1;
if(i <= m) set(i, v, lx, m, x << 1);
else set(i, v, m + 1, rx, x << 1 | 1);
tree[x] = merge(tree[x << 1], tree[x << 1 | 1]);
}
ar<int, 2> ans;
void get(int l, int r, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return;
if(lx >= l && rx <= r){
ans = merge(ans, tree[x]);
return;
} int m = (lx + rx) >> 1;
get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1);
}
}tree;
int l[N], r[N], res[N];
vector<int> Q[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
string s; cin >> s;
int q; cin >> q;
for(int i=0;i<q;i++){
cin >> l[i] >> r[i]; r[i]--;
Q[--l[i]].push_back(i);
}
deque<int> t;
for(int i=n-1;~i;i--){
if(s[i] == 'T'){
t.push_front(i);
} else {
tree.set(i, -1);
if(!t.empty()) tree.set(t.front(), 1), t.pop_front();
}
for(auto j : Q[i]){
int c = upper_bound(t.begin(), t.end(), r[j]) - t.begin();
tree.ans = {0, 0};
tree.get(i, r[j]);
res[j] = c + tree.ans[1];
}
}
for(int i=0;i<q;i++) cout<<res[i]<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
12244 KB |
Output is correct |
| 2 |
Correct |
8 ms |
12244 KB |
Output is correct |
| 3 |
Correct |
9 ms |
12212 KB |
Output is correct |
| 4 |
Correct |
10 ms |
12196 KB |
Output is correct |
| 5 |
Correct |
8 ms |
12184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
12244 KB |
Output is correct |
| 2 |
Correct |
8 ms |
12244 KB |
Output is correct |
| 3 |
Correct |
9 ms |
12212 KB |
Output is correct |
| 4 |
Correct |
10 ms |
12196 KB |
Output is correct |
| 5 |
Correct |
8 ms |
12184 KB |
Output is correct |
| 6 |
Correct |
60 ms |
16776 KB |
Output is correct |
| 7 |
Correct |
50 ms |
15896 KB |
Output is correct |
| 8 |
Correct |
55 ms |
16144 KB |
Output is correct |
| 9 |
Correct |
53 ms |
16604 KB |
Output is correct |
| 10 |
Correct |
54 ms |
16552 KB |
Output is correct |
| 11 |
Correct |
64 ms |
16844 KB |
Output is correct |
| 12 |
Correct |
62 ms |
16852 KB |
Output is correct |
| 13 |
Correct |
62 ms |
16744 KB |
Output is correct |
| 14 |
Correct |
57 ms |
16792 KB |
Output is correct |
| 15 |
Correct |
55 ms |
16744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
12244 KB |
Output is correct |
| 2 |
Correct |
8 ms |
12244 KB |
Output is correct |
| 3 |
Correct |
9 ms |
12212 KB |
Output is correct |
| 4 |
Correct |
10 ms |
12196 KB |
Output is correct |
| 5 |
Correct |
8 ms |
12184 KB |
Output is correct |
| 6 |
Correct |
60 ms |
16776 KB |
Output is correct |
| 7 |
Correct |
50 ms |
15896 KB |
Output is correct |
| 8 |
Correct |
55 ms |
16144 KB |
Output is correct |
| 9 |
Correct |
53 ms |
16604 KB |
Output is correct |
| 10 |
Correct |
54 ms |
16552 KB |
Output is correct |
| 11 |
Correct |
64 ms |
16844 KB |
Output is correct |
| 12 |
Correct |
62 ms |
16852 KB |
Output is correct |
| 13 |
Correct |
62 ms |
16744 KB |
Output is correct |
| 14 |
Correct |
57 ms |
16792 KB |
Output is correct |
| 15 |
Correct |
55 ms |
16744 KB |
Output is correct |
| 16 |
Correct |
527 ms |
46272 KB |
Output is correct |
| 17 |
Correct |
355 ms |
39860 KB |
Output is correct |
| 18 |
Correct |
451 ms |
42420 KB |
Output is correct |
| 19 |
Correct |
415 ms |
44560 KB |
Output is correct |
| 20 |
Correct |
495 ms |
45228 KB |
Output is correct |
| 21 |
Correct |
648 ms |
47448 KB |
Output is correct |
| 22 |
Correct |
542 ms |
46952 KB |
Output is correct |
| 23 |
Correct |
552 ms |
46108 KB |
Output is correct |
| 24 |
Correct |
575 ms |
46316 KB |
Output is correct |
| 25 |
Correct |
591 ms |
46332 KB |
Output is correct |
