#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n
const int N = 5e5;
struct SegTree {
///
struct Node {
int sum;
int mnSuf;
};
vector <Node> seg;
int n;
SegTree (int n) {
this-> n = n;
seg.resize (1 + 4 * n);
}
Node join (Node lNode, Node rNode) {
return {lNode.sum + rNode.sum, min (rNode.mnSuf, lNode.mnSuf + rNode.sum)};
}
void updatePos (int node, int lb, int rb, int pos, int val) {
if (lb == rb) {
seg[node] = {val, min (val, 0)};
return;
}
int mid = (lb + rb) / 2;
if (pos <= mid)
updatePos (node * 2, lb, mid, pos, val);
else
updatePos (node * 2 + 1, mid + 1, rb, pos, val);
seg[node] = join (seg[node * 2], seg[node * 2 + 1]);
}
Node queryRange (int node, int lb, int rb, int qL, int qR) {
if (qL <= lb && rb <= qR)
return seg[node];
int mid = (lb + rb) / 2;
Node ans = {0, 0};
if (qL <= mid)
ans = join (ans, queryRange (node * 2, lb, mid, qL, qR));
if (qR >= mid + 1)
ans = join (ans, queryRange (node * 2, mid + 1, rb, qL, qR));
return ans;
}
};
vector <pair <int, int>> qry[1 + N];
int val[1 + N];
int main () {
int n;
string votes;
cin >> n >> votes;
for (int i = 0; i < n; i++)
val[i + 1] = votes[i] == 'C' ? 1 : -1;
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
qry[l].pb ({r, i});
}
SegTree seg (n);
vector <int> stk;
for (int i = 1; i <= n; i++)
seg.updatePos (1, 1, n, i, val[i]);
vector <int> sol (q);
for (int i = n; i > 0; i--) {
if (val[i] == 1) {
if (stk.size ()) {
seg.updatePos (1, 1, n, stk.back (), -1);
stk.pop_back ();
}
}
else {
seg.updatePos (1, 1, n, i, 0);
stk.push_back (i);
}
for (pair <int, int> it : qry[i]) {
int l = i;
int r = it.first;
int index = it.second;
sol[index] = - seg.queryRange (1, 1, n, l, r).mnSuf + (upper_bound (stk.rbegin (), stk.rend (), r) - stk.rbegin ());
}
}
for (int x : sol)
cout << x << "\n";
cout << "\n";
return 0;
}
Compilation message
election.cpp:7:42: warning: missing terminating " character
7 | #define dbg(x) cerr << #x << " " << x << "\n
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
12288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
12288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
12288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
