#include <bits/stdc++.h>
int ri() {
int n;
scanf("%d", &n);
return n;
}
int64_t rs64() {
long long n;
scanf("%lld", &n);
return n;
}
struct AVL {
struct Node {
Node *l;
Node *r;
int key;
int val;
int sum;
int size;
int height;
Node *fetch() {
size = 1 + l->size + r->size;
height = 1 + std::max(l->height, r->height);
sum = val + l->sum + r->sum;
return this;
}
Node *rotate_l() {
Node *new_root = r;
r = new_root->l;
new_root->l = this;
return fetch(), new_root->fetch();
}
Node *rotate_r() {
Node *new_root = l;
l = new_root->r;
new_root->r = this;
return fetch(), new_root->fetch();
}
int height_diff() { return l->height - r->height; }
Node *balance() {
int dif = height_diff();
if (dif == 2) {
if (l->height_diff() < 0) l = l->rotate_l();
return rotate_r();
} else if (dif == -2) {
if (r->height_diff() > 0) r = r->rotate_r();
return rotate_l();
} else return fetch();
}
};
static Node *nodes, *NONE;
static int head;
Node *root = NONE;
AVL() {
if (!head) nodes[head++] = {NONE, NONE, 0, 0, 0, 0, 0};
}
Node *add(Node *node, int index, int val) {
if (node == NONE) return &(nodes[head++] = {NONE, NONE, index, val, val, 1, 1});
if (index < node->key) node->l = add(node->l, index, val);
else if (index > node->key) node->r = add(node->r, index, val);
else node->val += val;
return node->balance();
}
int sum(Node *node, int r) {
if (node == NONE) return 0;
if (r > node->key) return node->val + node->l->sum + sum(node->r, r);
else return sum(node->l, r);
}
void add(int index, int val) { root = add(root, index, val); }
int sum(int r) { return sum(root, r); }
};
AVL::Node *AVL::nodes = (Node *) malloc(sizeof(Node) * 10000000), *AVL::NONE = nodes;
int AVL::head = 0;
struct SegTree2D {
std::vector<AVL> data;
int n;
SegTree2D (int h_, int w_) {
for (n = 1; n < h_; n <<= 1);
data.resize(n * 2);
}
void add(int i, int j, int val) {
for (i += n; i; i >>= 1) data[i].add(j, val);
}
int sum(int x, int y) {
int l = 0, r = x;
int res = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (r & 1) res += data[--r].sum(y);
if (l & 1) res += data[l++].sum(y);
}
return res;
}
};
int main() {
int n = ri(), q = ri();
std::vector<bool> state(n);
{
std::string s;
std::cin >> s;
for (int i = 0; i < n; i++) state[i] = s[i] == '1';
}
std::set<std::pair<int, int> > range;
SegTree2D tree(n + 1, n + 1);
auto add = [&] (int l, int r, int val) {
tree.add(l, 0, val);
if (r < n) tree.add(l, r + 1, -val);
};
int time = 0;
auto toggle = [&] (int i) {
if (state[i]) {
auto itr = std::prev(range.upper_bound({i, 1000000000}));
if (itr->first < i) add(itr->first, i, q - time), range.insert({itr->first, i});
if (i + 1 < itr->second) add(i + 1, itr->second, q - time), range.insert({i + 1, itr->second});
add(itr->first, itr->second, time - q);
range.erase(itr);
} else {
auto itr = range.lower_bound({i, 0});
int l = i, r = i + 1;
if (itr != range.end() && itr->first == r) r = itr->second, add(itr->first, itr->second, time - q), range.erase(itr++);
if (itr != range.begin() && (--itr)->second == l) l = itr->first, add(itr->first, itr->second, time - q), range.erase(itr);
add(l, r, q - time);
range.insert({l, r});
}
state[i] = !state[i];
};
for (int i = 0; i < n; ) {
for (; i < n && !state[i]; i++);
if (i == n) break;
int old_i = i;
for (; i < n && state[i]; i++);
range.insert({old_i, i});
add(old_i, i, q);
}
for (int i = 0; i < q; i++) {
time++;
std::string type;
std::cin >> type;
if (type == "toggle") {
int i = ri() - 1;
toggle(i);
} else if (type == "query") {
int l = ri() - 1;
int r = ri() - 1;
int sum = tree.sum(l + 1, r + 1);
auto itr = range.upper_bound({l, 1000000000});
if (itr != range.begin() && std::prev(itr)->first <= l && std::prev(itr)->second >= r) sum -= q - i - 1;
std::cout << sum << std::endl;
}
}
return 0;
}
Compilation message
street_lamps.cpp: In function 'int ri()':
street_lamps.cpp:5:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
street_lamps.cpp: In function 'int64_t rs64()':
street_lamps.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &n);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
3 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
910 ms |
4900 KB |
Output is correct |
| 2 |
Correct |
1057 ms |
5280 KB |
Output is correct |
| 3 |
Correct |
1868 ms |
10864 KB |
Output is correct |
| 4 |
Correct |
4951 ms |
146768 KB |
Output is correct |
| 5 |
Correct |
4741 ms |
122412 KB |
Output is correct |
| 6 |
Execution timed out |
5028 ms |
155744 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
760 KB |
Output is correct |
| 2 |
Correct |
7 ms |
760 KB |
Output is correct |
| 3 |
Correct |
6 ms |
632 KB |
Output is correct |
| 4 |
Correct |
6 ms |
376 KB |
Output is correct |
| 5 |
Execution timed out |
5045 ms |
159572 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
504 KB |
Output is correct |
| 2 |
Correct |
6 ms |
632 KB |
Output is correct |
| 3 |
Correct |
6 ms |
632 KB |
Output is correct |
| 4 |
Correct |
6 ms |
768 KB |
Output is correct |
| 5 |
Correct |
2554 ms |
89904 KB |
Output is correct |
| 6 |
Correct |
3720 ms |
126076 KB |
Output is correct |
| 7 |
Execution timed out |
5003 ms |
155256 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
3 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
910 ms |
4900 KB |
Output is correct |
| 9 |
Correct |
1057 ms |
5280 KB |
Output is correct |
| 10 |
Correct |
1868 ms |
10864 KB |
Output is correct |
| 11 |
Correct |
4951 ms |
146768 KB |
Output is correct |
| 12 |
Correct |
4741 ms |
122412 KB |
Output is correct |
| 13 |
Execution timed out |
5028 ms |
155744 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
