This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
# include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 3;
struct node{
int sum, mn;
node(){
sum = mn = 0;
}
}
t[N * 4];
int n;
string s;
int q, ans[N];
vector < pair <int, int> > qe[N];
vector <int> st;
node _new;
node combine(node a, node b){
a.mn = min(b.mn, a.mn + b.sum);
a.sum += b.sum;
return a;
}
void build(int v = 1, int tl = 1, int tr = n){
if(tl == tr){
t[v].sum = (s[tl] == 'C'?1:-1);
t[v].mn = t[v].sum;
} else {
int tm = (tl + tr) >> 1;
build(v << 1, tl, tm);
build(v << 1 | 1, tm + 1, tr);
t[v] = combine(t[v << 1], t[v << 1 | 1]);
}
}
void upd(int pos, int val, int v = 1, int tl = 1, int tr = n){
if(tl == tr){
t[v].sum = t[v].mn = val;
} else {
int tm = (tl + tr) >> 1;
if(pos <= tm)
upd(pos, val, v << 1, tl, tm);
else
upd(pos, val, v << 1 | 1, tm + 1, tr);
t[v] = combine(t[v << 1], t[v << 1 | 1]);
}
}
node get(int l, int r, int v = 1, int tl = 1, int tr = n){
if(l > tr || tl > r)
return _new;
if(l <= tl && tr <= r)
return t[v];
int tm = (tl + tr) >> 1;
return combine(get(l, r, v << 1, tl, tm), get(l, r, v << 1 | 1, tm + 1, tr));
}
int main(){
cin >> n >> s >> q;
s = ' ' + s;
for(int i = 1; i <= q; i ++){
int l, r;
cin >> l >> r;
qe[l].emplace_back(r, i);
}
build();
for(int i = n; i >= 1; i --){
if(s[i] == 'T'){
st.push_back(i);
upd(i, 0);
} else if(!st.empty()){
upd(st.back(), -1);
st.pop_back();
}
for(int j = 0; j < (int)qe[i].size(); j ++){
int ret = upper_bound(st.rbegin(), st.rend(), qe[i][j].first) - st.rbegin();
ret -= min(get(i, qe[i][j].first).mn, 0);
ans[ qe[i][j].second ] = ret;
}
}
for(int i = 1; i <= q; i ++)
cout << ans[i] << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |