// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct node {
bool id = 0;
//fixed -> no negative pref sum
//not fixed -> any pref sum
int fixed_ans = 0;
int fixed_sum = 0;
int sum = 0;
int fixed_mn_suf = 0;
int mn_suf = 0;
int mn_pref = 0;
};
node comb(node a, node b) {
node c;
if(a.id) return b;
if(b.id) return a;
c.sum = a.sum + b.sum;
c.mn_suf = min(b.mn_suf, a.mn_suf + b.sum);
c.mn_pref = min(a.mn_pref, b.mn_pref + a.sum);
int add = 0;
if(a.fixed_sum + b.mn_pref < 0) add = -(a.fixed_sum + b.mn_pref);
c.fixed_sum = a.fixed_sum + b.sum + add;
c.fixed_ans = a.fixed_ans + add;
c.fixed_mn_suf = min(b.mn_suf + add, a.fixed_mn_suf + b.sum + add);
return c;
}
node idnode;
const int N = 5e5 + 42;
node st[4 * N];
string s;
void build(int v, int tl, int tr) {
if(tl == tr) {
if(s[tl] == 'C') {
st[v].fixed_ans = 0;
st[v].fixed_sum = 1;
st[v].sum = 1;
st[v].fixed_mn_suf = 0;
st[v].mn_suf = 0;
st[v].mn_pref = 0;
} else {
st[v].fixed_ans = 1;
st[v].fixed_sum = 0;
st[v].sum = -1;
st[v].fixed_mn_suf = 0;
st[v].mn_suf = -1;
st[v].mn_pref = -1;
}
} else {
int tm = (tl + tr) / 2;
build((v << 1), tl, tm);
build((v << 1) + 1, tm + 1, tr);
st[v] = comb(st[(v << 1)], st[(v << 1) + 1]);
}
}
node get(int v, int tl, int tr, int l, int r) {
if(l > r) return idnode;
if(l == tl && r == tr) return st[v];
int tm = (tl + tr) / 2;
return comb(get((v << 1), tl, tm, l, min(r, tm)), get((v << 1) + 1, tm + 1, tr, max(l, tm + 1), r));
}
void solve() {
int n, q;
cin >> n;
cin >> s;
build(1, 0, n - 1);
cin >> q;
while(q--) {
int l, r;
cin >> l >> r; l--; r--;
node res = get(1, 0, n - 1, l, r);
cout << res.fixed_ans - res.fixed_mn_suf << '\n';
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
idnode.id = 1;
int t = 1;
// cin >> t;
while(t--) solve();
return 0;
}
/*
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
