#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 7;
const int inf = 1e5 + 7;
struct node {
int val, lazy;
} pref[4 * N], suf[4 * N];
void push(int v, int tl, int tr) {
if(pref[v].lazy) {
pref[v].val += pref[v].lazy;
if(tl != tr) {
pref[2 * v + 1].lazy += pref[v].lazy;
pref[2 * v + 2].lazy += pref[v].lazy;
}
pref[v].lazy = 0;
}
}
void update(int v, int tl, int tr, int l, int r, int val) {
push(v, tl, tr);
if(l > r) return;
if(tl == l && tr == r) {
pref[v].lazy = val;
push(v, tl, tr);
return;
}
int tm = (tl + tr) / 2;
update(2 * v + 1, tl, tm, l, min(r, tm), val);
update(2 * v + 2, tm + 1, tr, max(l, tm + 1), r, val);
pref[v].val = min(pref[2 * v + 1].val, pref[2 * v + 2].val);
}
int get(int v, int tl, int tr, int l, int r) {
push(v, tl, tr);
if(l > r) return inf;
if(tl == l && tr == r) {
return pref[v].val;
}
int tm = (tl + tr) / 2;
int gl = get(2 * v + 1, tl, tm, l, min(r, tm));
int gr = get(2 * v + 2, tm + 1, tr, max(l, tm + 1), r);
return min(gl, gr);
}
void push2(int v, int tl, int tr) {
if(suf[v].lazy) {
suf[v].val += suf[v].lazy;
if(tl != tr) {
suf[2 * v + 1].lazy += suf[v].lazy;
suf[2 * v + 2].lazy += suf[v].lazy;
}
suf[v].lazy = 0;
}
}
void update2(int v, int tl, int tr, int l, int r, int val) {
push2(v, tl, tr);
if(l > r) return;
if(tl == l && tr == r) {
suf[v].lazy = val;
push2(v, tl, tr);
return;
}
int tm = (tl + tr) / 2;
update2(2 * v + 1, tl, tm, l, min(r, tm), val);
update2(2 * v + 2, tm + 1, tr, max(l, tm + 1), r, val);
suf[v].val = min(suf[2 * v + 1].val, suf[2 * v + 2].val);
}
int get2(int v, int tl, int tr, int l, int r) {
push2(v, tl, tr);
if(l > r) return inf;
if(tl == l && tr == r) {
return suf[v].val;
}
int tm = (tl + tr) / 2;
int gl = get2(2 * v + 1, tl, tm, l, min(r, tm));
int gr = get2(2 * v + 2, tm + 1, tr, max(l, tm + 1), r);
return min(gl, gr);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
string s;
cin >> s;
vector <int> pf(n + 1, 0), sf(n + 2, 0);
for(int i = 0; i < n; i++) {
pf[i + 1] = s[i] == 'C' ? 1 : -1;
pf[i + 1] += pf[i];
update(0, 1, n, i + 1, i + 1, pf[i + 1]);
}
for(int i = n - 1; i >= 0; i--) {
sf[i + 1] = s[i] == 'C' ? 1 : -1;
sf[i + 1] += sf[i + 2];
update2(0, 1, n, i + 1, i + 1, sf[i + 1]);
}
int q;
cin >> q;
for(int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
update(0, 1, n, l, r, -pf[l - 1]);
update2(0, 1, n, l, r, -sf[r + 1]);
int g1 = -get(0, 1, n, l, r);
int g2 = -get2(0, 1, n, l, r);
int ans = max(0, max(g1, g2));
cout << ans << '\n';
update(0, 1, n, l, r, pf[l - 1]);
update2(0, 1, n, l, r, sf[r + 1]);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
