#include <bits/stdc++.h>
std::string process(std::string c, int k) {
c[k] = 'R';
std::vector<int> lr, rl;
for (int i = k - 1; i >= 0; --i) {
if (c[i] == 'R') lr.push_back(i);
}
for (int i = k + 1; i < c.size(); ++i) {
if (c[i] == 'B') rl.push_back(i);
}
if (rl.empty()) {
for (int i = k; i < c.size(); ++i) c[i] = 'B';
} else if (lr.empty()) {
for (int i = 0; i <= rl[0]; i++) c[i] = 'R';
} else if (lr.size() >= rl.size()) {
int k = rl.size();
int pos = lr[k - 1];
for (int i = pos; i < c.size(); ++i) c[i] = 'B';
} else {
int k = lr.size();
int pos = rl[k - 1];
for (int i = 0; i <= pos; ++i) c[i] = 'R';
}
return c;
// c[k] = 'R';
// while (0 <= k && k < c.size()) {
// if (c[k] == 'R') {
// c[k] = 'B';
// k++;
// } else {
// c[k] = 'R';
// k--;
// }
// }
// return c;
}
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
std::cin >> n >> m;
std::string c;
std::cin >> c;
std::vector<int> a(m);
for (auto& i : a) std::cin >> i, --i;
if (n <= 0) {
int st = 0;
for (int i = 0; i < n; ++i) {
st |= (c[i] == 'R') << i;
}
std::vector<std::vector<int>> ss(1 << n, std::vector<int>(n));
for (int mask = 0; mask < 1 << n; ++mask) {
for (int i = 0; i < n; ++i) {
int m4sk = mask;
int ptr = i;
m4sk |= 1 << i;
while (0 <= ptr && ptr < n) {
m4sk ^= 1 << ptr;
if (~m4sk >> ptr & 1) {
ptr++;
} else {
ptr--;
}
}
ss[mask][i] = m4sk;
}
}
std::vector<int> qq(1 << n, -1);
std::vector<int> pos(m, -1);
std::vector<int> leader(m, -1);
std::vector<std::vector<std::pair<int, int>>> que(m);
int q;
std::cin >> q;
std::vector<int> ans(q);
for (int i = 0; i < q; ++i) {
int l, r;
std::cin >> l >> r;
--l, --r;
que[r].emplace_back(l, i);
}
auto get = [&](int u) -> int {
while (u != leader[u]) u = leader[u] = leader[leader[u]];
return u;
};
for (int i = 0; i < m; ++i) {
if (qq[st] == -1) {
qq[st] = i;
pos[i] = st;
leader[i] = i;
} else {
leader[i] = qq[st];
}
std::vector<int> nw(1 << n, -1);
for (int j = 0; j < 1 << n; ++j) {
if (qq[j] == -1) continue;
int k = ss[j][a[i]];
if (nw[k] != -1) {
leader[qq[j]] = nw[k];
} else {
nw[k] = qq[j];
pos[qq[j]] = k;
}
}
qq = nw;
for (auto [l, id] : que[i]) {
ans[id] = __builtin_popcount(pos[get(l)]);
}
}
for (auto i : ans) std::cout << i << '\n';
} else {
int q;
std::cin >> q;
int l, r;
std::cin >> l >> r;
--l, --r;
for (int i = l; i <= r; ++i) {
c = process(c, a[i]);
}
std::cout << std::count(c.begin(), c.end(), 'R');
}
}
Compilation message
Main.cpp: In function 'std::string process(std::string, int)':
Main.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | for (int i = k + 1; i < c.size(); ++i) {
| ~~^~~~~~~~~~
Main.cpp:13:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for (int i = k; i < c.size(); ++i) c[i] = 'B';
| ~~^~~~~~~~~~
Main.cpp:19:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for (int i = pos; i < c.size(); ++i) c[i] = 'B';
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
