#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }
const int INF = 1000 * 1000 * 1000;
struct Seg {
int n;
vi add, mn;
Seg(int n, vi &vals): n(n) {
add.assign(4 * n, 0);
mn.assign(4 * n, 0);
build(vals);
}
void propagate(int v, int tl, int tr) {
if(tl == tr || add[v] == 0)
return;
add[2 * v] += add[v];
add[2 * v + 1] += add[v];
mn[2 * v] += add[v];
mn[2 * v + 1] += add[v];
add[v] = 0;
}
void pull(int v) {
mn[v] = min(mn[2 * v], mn[2 * v + 1]);
}
void build(vi &vals, int v = 1, int tl = 0, int tr = -1) {
if(tr == -1) tr = n - 1;
if(tl == tr) {
mn[v] = vals[tl];
return;
}
int tm = (tl + tr) / 2;
build(vals, 2 * v, tl, tm);
build(vals, 2 * v + 1, tm + 1, tr);
pull(v);
}
void update(int l, int r, int val, int v = 1, int tl = 0, int tr = -1) {
if(tr == -1) tr = n - 1;
propagate(v, tl, tr);
if(l > r) return;
if(tl == l && r == tr) {
add[v] = val;
mn[v] += val;
return;
}
int tm = (tl + tr) / 2;
update(l, min(r, tm), val, 2 * v, tl, tm);
update(max(l, tm + 1), r, val, 2 * v + 1, tm + 1, tr);
pull(v);
}
int query(int l, int r, int v = 1, int tl = 0, int tr = -1) {
if(tr == -1) tr = n - 1;
propagate(v, tl, tr);
if(l > r) return INF;
if(tl == l && r == tr)
return mn[v];
int tm = (tl + tr) / 2;
int ql = query(l, min(r, tm), 2 * v, tl, tm);
int qr = query(max(l, tm + 1), r, 2 * v + 1, tm + 1, tr);
return min(ql, qr);
}
};
void solve() {
int n, q;
string s;
cin >> n >> s >> q;
vii qs[n];
forn(i, q) {
int l, r;
cin >> l >> r;
l--; r--;
qs[r].eb(l, i);
}
vi pr(n);
forn(i, n) {
pr[i] = (s[i] == 'C' ? 1 : -1);
if(i)
pr[i] += pr[i - 1];
}
Seg sg_pr(n, pr);
ordered_set turned_off;
vi ans(q);
forn(r, n) {
if(s[r] == 'T') {
turned_off.insert(r);
sg_pr.update(r, n - 1, +1);
} else if(sz(turned_off)) {
int w = *turned_off.rbegin();
turned_off.erase(w);
sg_pr.update(w, n - 1, -1);
}
for(ii li: qs[r]) {
int l = li.F, i = li.S;
int mn = sg_pr.query(l, r);
int rem = sz(turned_off) - turned_off.order_of_key(l);
ans[i] = -min(0, mn) + rem;
}
}
for(int a: ans)
cout << a << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// cout.tie(nullptr);
// freopen("optmilk.in", "r", stdin);
// freopen("optmilk.out", "w", stdout);
int t = 1;
// cin >> t;
while(t--) {
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
