#include <bits/stdc++.h>
#define x first
#define y second
using ll = long long;
using namespace std;
const int N = 1 << 17, M = 120120;
int st[2 * N], lazy[2 * N], a[N], b[M];
void build() {
for (int i = N - 1; i < 2 * N - 1; i++) {
st[i] = a[i - N + 1];
lazy[i] = -1;
}
for (int i = N - 2; i >= 0; i--) {
st[i] = st[2 * i + 1] + st[2 * i + 2];
lazy[i] = -1;
}
}
void update_seg(int l, int r, int v, int l1 = 0, int r1 = N - 1, int i = 0) {
if (l1 >= l && r1 <= r) {
st[i] = v * (r1 - l1 + 1);
lazy[i] = v;
return;
}
if (l1 > r || r1 < l) {
return;
}
if (lazy[i] != -1) {
st[2 * i + 1] = lazy[i] * (r1 - l1 + 1) / 2;
st[2 * i + 2] = lazy[i] * (r1 - l1 + 1) / 2;
lazy[2 * i + 1] = lazy[i];
lazy[2 * i + 2] = lazy[i];
lazy[i] = -1;
}
update_seg(l, r, v, l1, (l1 + r1) / 2, 2 * i + 1);
update_seg(l, r, v, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
st[i] = st[2 * i + 1] + st[2 * i + 2];
}
int get_sum(int l, int r, int l1 = 0, int r1 = N - 1, int i = 0) {
if (l1 >= l && r1 <= r) {
return st[i];
}
if (l1 > r || r1 < l) {
return 0;
}
if (lazy[i] != -1) {
st[2 * i + 1] = lazy[i] * (r1 - l1 + 1) / 2;
st[2 * i + 2] = lazy[i] * (r1 - l1 + 1) / 2;
lazy[2 * i + 1] = lazy[i];
lazy[2 * i + 2] = lazy[i];
lazy[i] = -1;
}
return get_sum(l, r, l1, (l1 + r1) / 2, 2 * i + 1) + get_sum(l, r, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
}
int down_l(int l, int r, int s, int l1 = 0, int r1 = N - 1, int i = 0) {
if (l1 > r || r1 < l) {
return -1;
}
if (s > st[i]) {
return -1;
}
if (l1 == r1 && s == st[i] && l1 >= l && r1 <= r) {
return l1;
} else if (l1 == r1) {
return -1;
}
if (lazy[i] != -1) {
st[2 * i + 1] = lazy[i] * (r1 - l1 + 1) / 2;
st[2 * i + 2] = lazy[i] * (r1 - l1 + 1) / 2;
lazy[2 * i + 1] = lazy[i];
lazy[2 * i + 2] = lazy[i];
lazy[i] = -1;
}
int v = get_sum(max(l, (l1 + r1) / 2 + 1), min(r, r1));
int left = down_l(l, r, s - v, l1, (l1 + r1) / 2, 2 * i + 1);
if (left == -1) {
return down_l(l, r, s, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
}
return left;
}
int down_r(int l, int r, int s, int l1 = 0, int r1 = N - 1, int i = 0) {
if (l1 > r || r1 < l) {
return -1;
}
if (r1 - l1 + 1 - s < st[i]) {
return -1;
}
if (l1 == r1 && s == 1 - st[i] && l1 >= l && r1 <= r) {
return l1;
} else if (l1 == r1) {
return -1;
}
if (lazy[i] != -1) {
st[2 * i + 1] = lazy[i] * (r1 - l1 + 1) / 2;
st[2 * i + 2] = lazy[i] * (r1 - l1 + 1) / 2;
lazy[2 * i + 1] = lazy[i];
lazy[2 * i + 2] = lazy[i];
lazy[i] = -1;
}
int v = max(min(r, (l1 + r1) / 2) - max(l, l1) + 1 - get_sum(max(l, l1), min(r, (l1 + r1) / 2)), 0);
int right = down_r(l, r, s - v, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
if (right == -1) {
return down_r(l, r, s, l1, (l1 + r1) / 2, 2 * i + 1);
}
return right;
}
int32_t main() {
int n, m;
cin >> n >> m;
string as;
cin >> as;
for (int i = 0; i < n; i++) {
a[i] = as[i] == 'B' ? 0 : 1;
}
for (int i = 0; i < m; i++) {
cin >> b[i]; b[i]--;
}
// cout << "!!\n";
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r; l--; r--;
build();
// cout << "!\n";
for (int i = l; i <= r; i++) {
int sl = get_sum(0, b[i] - 1), sr = n - b[i] - 1 - get_sum(b[i] + 1, n - 1);
// cout << sl << ' ' << sr << '\n';
if (sl < sr) {
int gr = down_r(b[i] + 1, n - 1, sl);
// cout << gr << '\n';
update_seg(0, gr, 1);
} else {
int gr = down_l(0, b[i] - 1, sr);
// cout << gr << '\n';
update_seg(gr, n - 1, 0);
}
}
cout << st[0] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
3164 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
3164 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
3164 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
3164 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
