#include <bits/stdc++.h>
using namespace std;
string s;
const int mxN = 5e5;
int n;
struct node {
int l, r, s, a;
};
node segtree[4*mxN+1];
void comb(node &a, node &b, node &c){
c.a = max(a.l+b.r, max(a.s+b.a, a.a + b.s));
c.l = max(a.l,a.s+b.l);
c.r = max(a.r+b.s,b.r);
c.s = a.s+b.s;
}
void build(int l = 0, int r = n-1, int idx = 0){
if (l == r){
if (s[l] == 'C'){
segtree[idx].s = -1;
} else {
segtree[idx].s = 1;
}
segtree[idx].l = segtree[idx].s;
segtree[idx].r = segtree[idx].s;
segtree[idx].a = 0;
if (segtree[idx].s > 0) segtree[idx].a = 1;
return;
}
int m = (l+r)/2;
build(l,m,2*idx+1);
build(m+1,r,2*idx+2);
comb(segtree[2*idx+1],segtree[2*idx+2],segtree[idx]);
segtree[idx].a = max(segtree[idx].a,0);
}
void query(int tl, int tr, node &res, int l = 0, int r = n-1, int idx = 0){
if (l > tr || r < tl){
return;
}
if (l >= tl && r <= tr){
comb(res,segtree[idx],res);
return;
}
int m = (l+r)/2;
query(tl,tr,res,l,m,2*idx+1);
query(tl,tr,res,m+1,r,2*idx+2);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int q;
cin >> n >> s >> q;
build();
int l,r;
node res;
for (int i =0; i < q; i++){
cin >> l >> r;
l -= 1;
r -= 1;
res.l = -1e9;
res.r = -1e9;
res.s = 0;
res.a = 0;
query(l,r,res);
cout << res.a << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
