#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX = 5e5 + 5;
int N, Q;
string s;
vector<pair<int,int>> query[MX];
int ans[MX];
struct segtree {
int t[4 * MX], lazy[4 * MX];
void push(int v, int l, int r) {
t[v] += lazy[v];
if(l != r) {
lazy[v * 2 + 0] += lazy[v];
lazy[v * 2 + 1] += lazy[v];
}
lazy[v] = 0;
}
void update(int v, int l, int r, int ql, int qr, int val) {
push(v, l, r);
if(l > qr || r < ql) return;
if(ql <= l && qr >= r) {
lazy[v] += val;
push(v, l, r);
return;
}
int mid = (l + r) >> 1;
update(v * 2 + 0, l, mid + 0, ql, qr, val);
update(v * 2 + 1, mid + 1, r, ql, qr, val);
t[v] = max(t[v * 2 + 0], t[v * 2 + 1]);
}
int query(int v, int l, int r, int ql, int qr) {
push(v, l, r);
if(l > qr || r < ql) return 0;
if(ql <= l && qr >= r) return t[v];
int mid = (l + r) >> 1;
return max(query(v * 2 + 0, l, mid + 0, ql, qr),
query(v * 2 + 1, mid + 1, r, ql, qr));
}
} st; // maintain suffix sum
struct fenwick {
int t[MX];
void upd(int v, int x) {
for(int i = v; i <= N; i += i & -i) t[i] += x;
}
int que(int x) {
int res = 0;
for(int i = x; i > 0; i -= i & -i) res += t[i];
return res;
}
int que(int x, int y) {
return que(y) - que(x - 1);
}
} ds;
/*
2 segtree, 1 maintain suffix sum butuh lazy dan range max
1 lagi BIT buat suffix nya sampe range (l, r) itu berapa yg diapus
*/
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> N >> s >> Q;
for(int i = 0; i < Q; i++) {
int l, r;
cin >> l >> r;
query[r].push_back({l, i});
}
vector<int> v;
for(int i = 1; i <= N; i++) {
int val = (s[i - 1] == 'C' ? -1 : 1);
st.update(1, 1, N, 1, i, val);
if(val == 1) {
v.push_back(i);
ds.upd(i, 1);
st.update(1, 1, N, 1, i, -1);
} else {
if(v.size()) {
st.update(1, 1, N, 1, v.back(), 1);
ds.upd(v.back(), -1);
v.pop_back();
}
}
for(auto [j, id] : query[i]) {
ans[id] = st.query(1, 1, N, j, i) + ds.que(j, i);
}
}
for(int i = 0; i < Q; i++) {
cout << ans[i] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
15196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
15196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
15196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
