#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
typedef long long llong;
const int MAXN = 300000 + 10;
const int MAXLOG = 19;
const int INF = 1e9;
int n, q;
char a[MAXN];
char s[MAXN];
std::mt19937 rng(69420);
struct MergeSortTree
{
struct Treap
{
struct Node
{
int sum;
int val;
bool toggled;
bool allToggles;
int x, y;
Node *left, *right;
Node()
{
x = y = sum = toggled = allToggles = 0;
left = right = nullptr;
}
Node(int _x, int _val, bool _toggled, int _y)
{
left = right = nullptr;
allToggles = toggled = _toggled;
sum = val = _val;
x = _x;
y = _y;
}
};
Node *root;
void recover(Node *curr)
{
if (curr == nullptr)
{
return;
}
curr->sum = curr->val;
curr->allToggles = curr->toggled;
if (curr->left != nullptr)
{
curr->sum += curr->left->sum;
curr->allToggles ^= curr->left->allToggles;
}
if (curr->right != nullptr)
{
curr->sum += curr->right->sum;
curr->allToggles ^= curr->right->allToggles;
}
}
void split(Node *curr, Node *&left, Node *&right, int value)
{
if (curr == nullptr)
{
left = right = nullptr;
return;
}
if (curr->x <= value)
{
left = curr;
split(curr->right, left->right, right, value);
recover(left);
} else
{
right = curr;
split(curr->left, left, right->left, value);
recover(right);
}
}
void merge(Node *&curr, Node *left, Node *right)
{
if (left == nullptr)
{
curr = right;
return;
}
if (right == nullptr)
{
curr = left;
return;
}
if (left->y > right->y)
{
curr = left;
merge(curr->right, left->right, right);
} else
{
curr = right;
merge(curr->left, left, right->left);
}
recover(curr);
}
void update(int x, int val)
{
Node *ll, *lr, *l, *r;
split(root, l, r, x);
split(l, ll, lr, x - 1);
if (lr != nullptr)
{
lr->val += val;
lr->toggled ^= 1;
recover(lr);
} else
{
lr = new Node(x, val, 1, rng());
}
merge(l, ll, lr);
merge(root, l, r);
}
std::pair <int,bool> query(int from)
{
Node *l, *r;
split(root, l, r, from - 1);
int res = 0;
bool toggled = 0;
if (r != nullptr)
{
res = r->sum;
toggled = r->allToggles;
}
merge(root, l, r);
return {res, toggled};
}
};
Treap tree[4*MAXN];
void update(int l, int r, int node, int queryRow, int queryCol, int queryVal)
{
tree[node].update(queryCol, queryVal);
if (l == r)
{
return;
}
int mid = (l + r) / 2;
if (queryRow <= mid) update(l, mid, 2*node, queryRow, queryCol, queryVal);
else update(mid + 1, r, 2*node + 1, queryRow, queryCol, queryVal);
}
std::pair <int,bool> query(int l, int r, int node, int queryRow, int queryCol)
{
if (l >= queryRow)
{
return tree[node].query(queryCol);
}
int mid = (l + r) / 2;
std::pair <int,bool> res = query(mid + 1, r, 2*node + 1, queryRow, queryCol);
if (queryRow <= mid)
{
auto add = query(l, mid, 2*node, queryRow, queryCol);
res.first += add.first;
res.second ^= add.second;
}
return res;
}
void update(int row, int col, int val)
{
if (row == 0 || col == 0)
{
return;
}
update(1, n, 1, row, col, val);
}
std::pair <int,bool> query(int row, int col)
{
return query(1, n, 1, row, col);
}
};
struct Fenwick
{
int tree[MAXN];
void update(int pos, int val)
{
for (int idx = pos ; idx <= n ; idx += idx & (-idx))
{
tree[idx] += val;
}
}
int query(int pos)
{
int res = 0;
for (int idx = pos ; idx > 0 ; idx -= idx & (-idx))
{
res += tree[idx];
}
return res;
}
int findKth(int k)
{
int pos = 0;
for (int log = MAXLOG - 1 ; log >= 0 ; --log)
{
if (pos + (1 << log) <= n && tree[pos + (1 << log)] < k)
{
pos += (1 << log);
k -= tree[pos];
}
}
return pos + 1;
}
};
Fenwick fenwick;
MergeSortTree tree;
void update(int fromX, int fromY, int toX, int toY, int val)
{
fromX--; fromY--;
tree.update(toX, toY, val);
tree.update(fromX, toY, -val);
tree.update(toX, fromY, -val);
tree.update(fromX, fromY, val);
}
int query(int r, int c, int time)
{
auto [res, myState] = tree.query(r, c);
if (myState == 1)
{
res += time;
}
return res;
}
void toggle(int idx, int time)
{
int res = fenwick.query(idx);
int lPos = fenwick.findKth(res - (s[idx] == '0'));
int rPos = fenwick.findKth(res + 1) - 1;
update(lPos, idx, idx, rPos, (s[idx] == '1' ? time : -time));
fenwick.update(idx, -(1 ^ (s[idx] - '0')));
s[idx] = '0' + ('1' - s[idx]);
fenwick.update(idx, (1 ^ (s[idx] - '0')));
}
void solve()
{
for (int i = 1 ; i <= n ; ++i)
{
s[i] = '0';
fenwick.update(i, 1);
}
for (int i = 1 ; i <= n ; ++i)
{
if (a[i] == '1')
{
toggle(i, 0);
}
}
for (int i = 1 ; i <= q ; ++i)
{
std::string qType;
std::cin >> qType;
if (qType == "toggle")
{
int pos;
std::cin >> pos;
toggle(pos, i);
} else
{
int l, r;
std::cin >> l >> r;
std::cout << query(l, r - 1, i) << '\n';
}
}
}
void input()
{
std::cin >> n >> q;
std::cin >> a + 1;
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
Compilation message
street_lamps.cpp: In function 'void input()':
street_lamps.cpp:313:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
313 | std::cin >> a + 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
527 ms |
3484 KB |
Output is correct |
| 2 |
Correct |
865 ms |
7280 KB |
Output is correct |
| 3 |
Correct |
1920 ms |
14844 KB |
Output is correct |
| 4 |
Execution timed out |
5039 ms |
290416 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
3164 KB |
Output is correct |
| 2 |
Correct |
8 ms |
3164 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
3308 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2908 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3164 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
3164 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
