#include <bits/stdc++.h>
using namespace std;
struct Tree {
vector<int> info, tags;
Tree(int size) {
info.resize(size*4, 0);
tags.resize(size*4);
}
void pushdown(int x) {
info[x] += tags[x];
if (x*2 < tags.size()) tags[x*2] += tags[x];
if (x*2+1 < tags.size()) tags[x*2+1] += tags[x];
tags[x] = 0;
}
void update(int l, int r, int x, int xl, int xr, int tag) {
if (l > r) return;
if (l == xl && r == xr) {
tags[x] += tag;
} else {
int xm = (xl+xr)/2;
update(l, min(r,xm), x*2, xl, xm, tag);
update(max(l,xm+1), r, x*2+1, xm+1, xr, tag);
pushdown(x*2); pushdown(x*2+1);
info[x] = min(info[x*2], info[x*2+1]);
}
}
int query(int l, int r, int x, int xl, int xr) {
if (l > r) return 1<<30;
pushdown(x);
if (l == xl && r == xr) {
return info[x];
} else {
int xm = (xl+xr)/2;
int left = query(l, min(r,xm), x*2, xl, xm);
int right = query(max(l,xm+1), r, x*2+1, xm+1, xr);
return min(left, right);
}
}
};
struct BIT {
vector<int> data;
BIT(int size) {
data.resize(size+1);
}
void update(int x, int delta) {
while (x < data.size()) {
data[x] += delta;
x += x & (-x);
}
}
int query(int x) {
int ans = 0;
while (x > 0) {
ans += data[x];
x -= x & (-x);
}
return ans;
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int N;
cin >> N;
string s;
cin >> s;
int Q;
cin >> Q;
vector<pair<int,int>> queries(Q);
for (int i=0; i<Q; i++) {
int L, R;
cin >> L >> R;
queries[i] = {L-1, R-1};
}
vector<int> order(Q);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) -> bool {
return queries[i].first > queries[j].first;
});
int L = N-1;
set<int> Xs;
BIT left(N);
Tree right(N);
vector<int> ans(N);
for (int i=0; i<Q; i++) {
pair<int,int> q = queries[order[i]];
while (L >= q.first) {
if (s[L] == 'C') {
if (!Xs.empty()) {
int idx = *Xs.begin();
left.update(idx+1, -1);
right.update(0, idx, 1, 0, N-1, -1);
Xs.erase(idx);
}
right.update(0, L, 1, 0, N-1, +1);
} else {
Xs.insert(L);
left.update(L+1, +1);
}
L -= 1;
}
int R = q.second;
int base = left.query(R+1);
int extra = right.query(L+1, R, 1, 0, N-1);
int next = R == N-1 ? 0 : right.query(R+1, R+1, 1, 0, N-1);
ans[order[i]] = base - min(0, extra - next);
}
for (int i=0; i<Q; i++) {
cout << ans[i] << "\n";
}
return 0;
}
Compilation message
election.cpp: In member function 'void Tree::pushdown(int)':
election.cpp:13:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | if (x*2 < tags.size()) tags[x*2] += tags[x];
| ~~~~^~~~~~~~~~~~~
election.cpp:14:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | if (x*2+1 < tags.size()) tags[x*2+1] += tags[x];
| ~~~~~~^~~~~~~~~~~~~
election.cpp: In member function 'void BIT::update(int, int)':
election.cpp:49:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | while (x < data.size()) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
