#include <iostream>
#include <vector>
#define left (id+1)
#define mid ((l+r)/2)
#define right (id+2*(mid-l+1))
int k;
struct seg
{
std::vector<std::pair<int, int> > arr;
std::pair<int, int> merge(std::pair<int, int> l, std::pair<int, int> r) {
int change = std::min(l.second, r.first);
return {l.first + r.first - change, r.second + l.second - change};
}
void update(int x, std::pair<int, int> val, int id = 0, int l = 0, int r = k-1) {
if(l == r) {
arr[id] = val;
return;
}
if(x <= mid)
update(x, val, left, l, mid);
else
update(x, val, right, mid+1, r);
arr[id] = merge(arr[left], arr[right]);
}
std::pair<int, int> query(int x, int y, int id = 0, int l = 0, int r = k-1) {
if(y < l || r < x)
return {0, 0};
if(x <= l && r <= y)
return arr[id];
return merge(query(x, y, left, l, mid), query(x, y, right, mid+1, r));
}
};
signed main() {
std::cin >> k;
std::string s;
std::cin >> s;
seg forw, back;
forw.arr = back.arr = std::vector<std::pair<int, int> >(2*k-1, {0, 0});
for(int i = 0; i < k; i++) {
if(s[i] == 'C') {
forw.update(i, {0, 1});
back.update(i, {1, 0});
}
else {
forw.update(i, {1, 0});
back.update(i, {0, 1});
}
}
int q;
std::cin >> q;
while(q--) {
int l, r;
std::cin >> l >> r;
l--; r--;
std::cout << std::max(forw.query(l, r).first, back.query(l, r).second) << std::endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
