#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int) 3e5 + 7;
int sol[107][107];
int n, q;
string s;
struct Operation {
bool type;
int a;
int b;
};
vector<Operation> op;
int subtask() {
if (n <= 100 && q <= 100) {
return 1;
}
for (auto &it : op) {
if (it.type == 1 && it.b - it.a != 1) {
return 3;
}
}
return 2;
}
int nodes = 0;
struct DSU { /// partially persistent dsu
vector<vector<pair<int, int>>> par;
int time = 0;
DSU(int n) : par(n + 1, {{-1, 0}}) {
}
bool unite(int u, int v) {
time++;
if ((u = root(u, time)) == (v = root(v, time))) return 0;
if (par[u].back().first > par[v].back().first) {
swap(u, v);
}
par[u].push_back({par[u].back().first + par[v].back().first, time});
par[v].push_back({u, time});
return 1;
}
bool same(int u, int v, int t) {
return root(u, t) == root(v, t);
}
int root(int u, int t) { /// root of u at time t
if (par[u].back().first >= 0 && par[u].back().second <= t) {
return root(par[u].back().first, t);
}
return u;
}
int size(int u, int t) { /// size of the component of u at time t
u = root(u, t);
int low = 0, high = (int) par[u].size() - 1, ans = 0;
while (low <= high) {
int mid = (low + high) / 2;
if (par[u][mid].second <= t) {
ans = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return -par[u][ans].first;
}
};
int a[N];
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
// freopen("input", "r", stdin);
cin >> n >> q >> s;
s = "#" + s;
for (int iq = 1; iq <= q; iq++) {
string t;
cin >> t;
if (t == "toggle") {
int a;
cin >> a;
op.push_back({0, a, -1});
} else {
int a, b;
cin >> a >> b;
op.push_back({1, a, b});
}
}
if (subtask() == 1) {
for (int i = 1; i <= n; i++) {
if (s[i] == '1') {
int j = i;
while (j <= n && s[j] == '1') {
sol[i][j + 1]++;
j++;
}
}
}
for (auto &it : op) {
if (it.type == 1) {
cout << sol[it.a][it.b] << "\n";
} else {
int pos = it.a;
s[pos] ^= '0' ^ '1';
}
for (int i = 1; i <= n; i++) {
if (s[i] == '1') {
int j = i;
while (j <= n && s[j] == '1') {
sol[i][j + 1]++;
j++;
}
}
}
}
return 0;
}
if (subtask() == 2) {
vector<vector<pair<int, int>>> active(n + 1);
for (int i = 1; i <= n; i++) {
if (s[i] == '1') {
active[i].push_back({0, -1});
}
}
for (int i = 0; i < q; i++) {
if (op[i].type == 0) {
int pos = op[i].a;
if (s[pos] == '0') {
s[pos] = '1';
active[pos].push_back({i + 1, -1});
} else {
s[pos] = '0';
active[pos].back().second = i;
}
}
}
vector<vector<int>> sp(n + 1);
for (int i = 1; i <= n; i++) {
if (s[i] == '1') {
active[i].back().second = q;
}
if ((int) active[i].size() == 0) {
continue;
}
sp[i].resize((int) active[i].size());
sp[i][0] = active[i][0].second - active[i][0].first + 1;
for (int j = 1; j < (int) active[i].size(); j++) {
sp[i][j] = sp[i][j - 1] + active[i][j].second - active[i][j].first + 1;
}
}
function<int(int, int)> get = [&](int pos, int t) {
int low = 0, high = (int) active[pos].size() - 1, x = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (active[pos][mid].second <= t) {
low = mid + 1;
x = mid;
} else {
high = mid - 1;
}
}
int sol = 0;
if (x != -1) {
sol += sp[pos][x];
}
if (x + 1 < (int) active[pos].size() && active[pos][x + 1].first <= t) {
sol += t - active[pos][x + 1].first + 1;
}
return sol;
};
for (int i = 0; i < q; i++) {
if (op[i].type == 1) {
assert(op[i].a + 1 == op[i].b);
cout << get(op[i].a, i) << "\n";
}
}
return 0;
}
if (subtask() == 3) {
DSU t(n + 1);
for (int i = 1; i <= n; i++) {
if (s[i] == '1') {
t.unite(i, i + 1);
a[t.time] = 1;
}
}
for (int i = 2; i <= q + 1; i++) {
if (op[i - 2].type == 0) {
t.unite(op[i - 2].a, op[i - 2].a + 1);
a[t.time] = i;
} else {
int low = 1, high = i, sol = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (t.same(op[i - 2].a, op[i - 2].b, mid)) {
sol = a[mid];
high = mid - 1;
} else {
low = mid + 1;
}
}
if (sol == -1) {
cout << "0\n";
} else {
cout << i - sol << "\n";
}
}
}
return 0;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
6620 KB |
Output is correct |
| 2 |
Correct |
65 ms |
6548 KB |
Output is correct |
| 3 |
Correct |
73 ms |
6576 KB |
Output is correct |
| 4 |
Correct |
123 ms |
31964 KB |
Output is correct |
| 5 |
Correct |
132 ms |
38000 KB |
Output is correct |
| 6 |
Correct |
119 ms |
32464 KB |
Output is correct |
| 7 |
Correct |
96 ms |
19644 KB |
Output is correct |
| 8 |
Correct |
151 ms |
38992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
372 KB |
Output is correct |
| 8 |
Correct |
68 ms |
6620 KB |
Output is correct |
| 9 |
Correct |
65 ms |
6548 KB |
Output is correct |
| 10 |
Correct |
73 ms |
6576 KB |
Output is correct |
| 11 |
Correct |
123 ms |
31964 KB |
Output is correct |
| 12 |
Correct |
132 ms |
38000 KB |
Output is correct |
| 13 |
Correct |
119 ms |
32464 KB |
Output is correct |
| 14 |
Correct |
96 ms |
19644 KB |
Output is correct |
| 15 |
Correct |
151 ms |
38992 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
