#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
struct Segtree {
struct Node {
int sum = 0, lc = 0, rc = 0;
Node() {}
Node(int num) : sum(num) {}
void addsum(const Node &l, const Node &r) {
sum = l.sum + r.sum;
}
};
vector<Node> nodes;
int n;
int new_node() {
nodes.emplace_back();
return nodes.size() - 1;
}
void update(int node, int left, int right, int idx, int val) {
if(left == idx && idx == right) {
nodes[node].sum += val;
return;
}
int mid = (left + right) / 2;
if(idx <= mid) {
if (!nodes[node].lc) {
nodes[node].lc = new_node();
}
update(nodes[node].lc, left, mid, idx, val);
}
if(idx > mid) {
if (!nodes[node].rc) {
nodes[node].rc = new_node();
}
update(nodes[node].rc, mid + 1, right, idx, val);
}
nodes[node].addsum(nodes[nodes[node].lc], nodes[nodes[node].rc]);
}
void add(int index, int val) {
update(1, 0, n - 1, index, val);
}
Node query(int node, int left, int right, int x, int y) {
if(node == 0) {
return {};
}
if(x <= left && right <= y) {
return nodes[node];
}
int mid = (left + right) / 2;
if(y <= mid) {
return query(nodes[node].lc, left, mid, x, y);
}
else if(x > mid) {
return query(nodes[node].rc, mid + 1, right, x, y);
}
return Node(query(nodes[node].lc, left, mid, x, y).sum + query(nodes[node].rc, mid + 1, right, x, y).sum);
}
int query_sum(int l, int r) {
return query(1, 0, n - 1, l, r).sum;
}
Segtree(int _n) : n(_n) {
nodes.emplace_back();
nodes.emplace_back();
}
Segtree() {}
};
struct BIT {
int maxsz;
vector<Segtree> bit;
void add(int r, int c, int v) {
if (r == maxsz || c == maxsz) {
return;
}
for (++r; r <= maxsz; r += (r & -r)) {
bit[r].add(c, v);
}
}
void submatrixadd(int r1, int c1, int r2, int c2, int to_add) {
add(r2 + 1, c2 + 1, to_add);
add(r2 + 1, c1, -to_add);
add(r1, c2 + 1, -to_add);
add(r1, c1, to_add);
}
int psum(int r, int c) {
int ret = 0;
for (++r; r; r -= (r & -r)) {
ret += bit[r].query_sum(0, c);
}
return ret;
}
BIT(int rows, int cols) : maxsz(rows) {
bit.resize(maxsz + 1);
for (int i = 1; i <= maxsz; ++i) {
bit[i] = Segtree(cols);
}
}
};
int main() {
int n, q;
string lightstatus;
set<int> off;
cin >> n >> q;
cin >> lightstatus;
BIT bit(n + 1, n + 1);
int start = -1;
for (int i = 0; i < n; ++i) {
if (lightstatus[i] == '1') {
if (start == -1) {
start = i;
}
if (i == n - 1) {
bit.submatrixadd(start, start, i + 1, i + 1, q);
}
}
else {
off.insert(i);
if (start != -1) {
bit.submatrixadd(start, start, i, i, q);
}
start = -1;
}
}
off.insert(-1);
off.insert(n);
for (int i = 0, a, b; i < q; ++i) {
string type;
cin >> type;
int remaintime = q - (i + 1);
if (type == "toggle") {
cin >> a;
--a;
int l = *prev(off.lower_bound(a)) + 1;
int r = *off.upper_bound(a);
if(lightstatus[a] == '0') {
bit.submatrixadd(a + 1, l, r, a, remaintime);
}
else {
bit.submatrixadd(a + 1, l, r, a, -1 * remaintime);
}
if (lightstatus[a] == '1') {
off.insert(a);
lightstatus[a] = '0';
}
else {
off.erase(a);
lightstatus[a] = '1';
}
}
else {
cin >> a >> b;
--a;
--b;
if (a < b) {
swap(a, b);
}
if (off.lower_bound(a) == off.lower_bound(b)) {
cout << bit.psum(a, b) - remaintime << '\n'; // overcount
}
else {
cout << bit.psum(a, b) << endl;
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
576 ms |
4964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
