#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
const int MN = 500001;
int A[MN], Re[MN];
int n, q;
vector<ii> Q[MN];
stack<int> PozDez;
namespace AINT {
int V[4 * MN], Lz[4 * MN], Pmin[4 * MN], Vmin[4 * MN];
void init(int u = 1, int s = 1, int d = n) {
V[u] = Lz[u] = Vmin[u] = 0;
Pmin[u] = s;
if(s != d) {
init(u << 1, s, (s + d) >> 1);
init(u << 1 | 1, ((s + d) >> 1) + 1, d);
}
}
void prop(int u, int s, int d) {
V[u] += Lz[u];
Vmin[u] += Lz[u];
if(s != d) {
Lz[u << 1] += Lz[u];
Lz[u << 1 | 1] += Lz[u];
}
Lz[u] = 0;
}
void add(int l, int r, int v, int u = 1, int s = 1, int d = n) {
prop(u, s, d);
if(d < l || r < s) {
return;
}
if(l <= s && d <= r) {
Lz[u] = v;
prop(u, s, d);
return;
}
add(l, r, v, u << 1, s, (s + d) >> 1);
add(l, r, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
if(Vmin[u << 1] <= Vmin[u << 1 | 1]) {
Vmin[u] = Vmin[u << 1];
Pmin[u] = Pmin[u << 1];
} else {
Vmin[u] = Vmin[u << 1 | 1];
Pmin[u] = Pmin[u << 1 | 1];
}
}
int poz_neg() {
if(Vmin[1] >= 0) return -1;
assert(Vmin[1] == -1);
return Pmin[1];
}
}
namespace AINT2 {
int V[4 * MN], SufMin[4 * MN];
void update(int p, int v, int u = 1, int s = 1, int d = n) {
if(d < p || p < s) return;
if(s == d) {
V[u] = v;
SufMin[u] = min(0, v);
return;
}
update(p, v, u << 1, s, (s + d) >> 1);
update(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
V[u] = V[u << 1] + V[u << 1 | 1];
SufMin[u] = min(SufMin[u << 1 | 1], SufMin[u << 1] + V[u << 1 | 1]);
}
pair<int, int> query(int l, int r, int u = 1, int s = 1, int d = n) { ///(sum, sufmin)
if(d < l || r < s) return {0, 0};
if(l <= s && d <= r) return {V[u], SufMin[u]};
ii r1 = query(l, r, u << 1, s, (s + d) >> 1), r2 = query(l, r, u << 1 | 1, ((s + d) >> 1) + 1, d);
return {r1.first + r2.first, min(r2.first + r1.second, r2.second)};
}
}
namespace AIB {
int V[MN];
int update(int p, int v) {
while(p < MN) {
V[p] += v;
p += p & -p;
}
}
int f(int p) {
int r = 0;
while(p) {
r += V[p];
p -= p & -p;
}
return r;
}
int query(int l, int r) {
if(!l) return f(r);
return f(r) - f(l - 1);
}
}
int main() {
cin >> n;
for(int i = 1; i <= n; ++i) {
char c; cin >> c;
A[i] = (c == 'C') ? 1 : -1;
}
cin >> q;
for(int i = 1; i <= q; ++i) {
int l, r;
cin >> l >> r;
Q[l].push_back({r, i});
}
int nr_dez = 0;
AINT::init();
for(int i = n; i >= 1; --i) {
///adaugam i
AINT::add(i, n, A[i]);
AINT2::update(i, A[i]);
if(A[i] == 1) {
if(!PozDez.empty()) {
int p1 = PozDez.top();
// printf("L-am activat pe %d\n", p1);
AIB::update(p1, -1);
AINT::add(p1, n, -1);
AINT2::update(p1, -1);
PozDez.pop();
}
}
else {
int p = AINT::poz_neg();
if(p != -1) {
AINT::add(p, n, 1);
// printf("L-am deazactivat pe %d\n", p);
AIB::update(p, 1);
AINT2::update(p, 0);
PozDez.push(p);
}
}
for(auto it : Q[i]) {
int r = it.first, pre = it.second;
Re[pre] = AIB::query(i, r) + max(0, -AINT2::query(i, r).second);
}
}
for(int i = 1; i <= q; ++i)
cout << Re[i] << "\n";
return 0;
}
Compilation message
election.cpp: In function 'int AIB::update(int, int)':
election.cpp:92:5: warning: no return statement in function returning non-void [-Wreturn-type]
92 | }
| ^
election.cpp: In function 'int main()':
election.cpp:119:9: warning: unused variable 'nr_dez' [-Wunused-variable]
119 | int nr_dez = 0;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
24652 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
24652 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
24652 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
