#include <bits/stdc++.h>
using namespace std;
constexpr int inf = 1e9;
int N;
int segSize;
struct Segment {
Segment *left = nullptr, *right = nullptr;
bool used = false;
int l, r, mid;
int val = 0, lazy = 0;
Segment(int l, int r) : l(l), r(r), mid((r + l) / 2) {
}
void sparse() {
if (used) return;
used = true;
if (r - l > 1) {
left = new Segment(l,mid);
right = new Segment(mid,r);
}
}
void push() {
if (lazy != 0) {
val += (r - l) * lazy;
if (r - l > 1) {
left->lazy+=lazy;
right->lazy+=lazy;
}
lazy = 0;
}
}
int q(int a, int b) {
sparse();
push();
if (a >= r || b <= l) return 0;
if (a <= l && b >= r) return val;
return left->q(a,b) + right->q(a,b);
}
void update(int a, int b, int v) {
sparse();
push();
if (a >= r || b <= l) return;
if (a <= l && b >= r) {
lazy += v;
push();
return;
}
left->update(a,b,v);
right->update(a,b,v);
val = left->val + right->val;
}
void update(int x, int u) {
sparse();
push();
if (r - l <= 1) {
val += u;
return;
}
if (x < mid)
left->update(x,u);
else
right->update(x,u);
val = left->val + right->val;
}
int getRight(int a, int b) {
sparse();
push();
while (b > a) {
int m = a + (b - a) / 2;
if (q(m,b + 1) != b + 1 - m) {
a = m + 1;
} else
b = m;
}
return a;
}
int getLeft(int a, int b) {
sparse();
push();
while (b > a) {
int m = a + (b - a) / 2;
if (q(a,m + 1) != m + 1 - a) {
b = m;
} else
a = m + 1;
}
return a;
}
};
struct Segment2D {
Segment2D *left = nullptr, *right = nullptr;
int l, r, mid;
bool used = false;
Segment *val, *sum;
Segment2D(int l, int r) : l(l), r(r), mid((l + r) / 2) {
val = new Segment(0,segSize);
sum = new Segment(0,segSize);
}
void sparse() {
if (used) return;
used = true;
if (r - l > 1) {
left = new Segment2D(l,mid);
right = new Segment2D(mid,r);
}
}
int q(int a, int b, int aL, int aR) {
sparse();
if (a >= r || b <= l) return 0;
if (a <= l && b >= r) return val->q(aL,aR) + sum->q(aL,aR);
int res = val->q(aL,aR);
return res + left->q(a,b,aL,aR) + right->q(a,b,aL,aR);
}
void update(int a, int b, int aL,int aR, int v) {
sparse();
if (a >= r || b <= l) return;
if (a <= l && b >= r) {
val->update(aL,aR,v);
return;
}
left->update(a,b,aL,aR,v);
right->update(a,b,aL,aR,v);
sum->update(aL,aR,v);
}
};
Segment *checkSeg;
set<int> zeroes;
set<int> zeroesRev;
pair<int,int> getRanges(int i) {
auto it = zeroes.lower_bound(i);
int r;
if (it == zeroes.end()) r = N - 1;
else r = *it - 1;
auto it2 = zeroesRev.lower_bound(-i);
int l;
if (it2 == zeroesRev.end()) l = 0;
else l = -*it2 + 1;
return {l,r};
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n, q; cin >> n>> q;
N = n;
string s; cin >> s;
vector<int> time(n,0);
checkSeg = new Segment(0,n);
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '1') checkSeg->update(i,1);
else {
zeroes.insert(i);
zeroesRev.insert(-i);
}
}
// Insert A (l, r)
// Erase A, (l, r)
// Check b, a (l, r)
vector<tuple<int,int,int,int,int>> queries; // A,1, 1, (l, r) (insert)
vector<bool> qAsk(q);
// B, 3, a (l, r)
// B -1, 2, a (l, r)
for (int i = 0; i < q; ++i) {
string type; cin >> type;
qAsk[i] = type == "query";
if (type == "toggle") {
int x; cin >> x;
x--;
if (s[x] == '1') {
auto [l, r] = getRanges(x);
int t = time[l];
queries.emplace_back(l,1,1,t,i + 1);
queries.emplace_back(r,3,l,t,i + 1);
checkSeg->update(x,-1);
if (s[l] == '1') time[l] = i + 1;
if (x + 1 < n && s[x + 1] == '1') time[x + 1] = i + 1;
} else {
if ( x - 1 >= 0 && s[x - 1] == '1') {
auto [l, r] = getRanges(x - 1);
int t = time[l];
queries.emplace_back(l,1,1,t,i + 1);
queries.emplace_back(r,3,l,t,i + 1);
time[l] = i + 1;
}
if (x + 1 < n && s[x + 1] == '1') {
auto [l, r] = getRanges(x + 1);
int t = time[l];
queries.emplace_back(l,1,1,t,i + 1);
queries.emplace_back(r,3,l,t,i + 1);
time[l] = i + 1;
}
checkSeg->update(x,1);
if (s[x] == '0') {
zeroes.erase(x);
zeroesRev.erase(-x);
}
if (s[x] == '1') {
zeroes.insert(x);
zeroesRev.insert(-x);
}
auto [l, r] = getRanges(x);
time[l] = i + 1;
}
if (s[x] == '0') {
zeroes.erase(x);
zeroesRev.erase(-x);
}
s[x] = s[x] == '1' ? '0' : '1';
if (s[x] == '0') {
zeroes.insert(x);
zeroesRev.insert(-x);
}
} else {
int a, b; cin >> a >> b;
a--;
b--;
b--;
queries.emplace_back(b,2,a,0,i + 1);
}
}
for (int x = 0; x < n; ++x) {
if (s[x] == '1') {
auto [l, r] = getRanges(x);
int t = time[l];
if (t == q) continue;
queries.emplace_back(l,1,1,t,q);
queries.emplace_back(r,3,l,t,q);
checkSeg->update(l,r,0);
time[l] = q;
}
}
std::sort(queries.begin(), queries.end());
segSize = q;
Segment2D seg(-1,N);
vector<int> ans(q);
int global = 0;
for (auto [a, t, b, l, r] : queries) {
if (t == 1) {
// Create
seg.update(a,inf,l,r,1);
global+=r - l;
}
if (t == 2) {
ans[r - 1] = seg.q(b,b+1,l,r);
}
if (t == 3) {
seg.update(b,inf,l,r,-1);
global-= r - l;
}
}
for (int i = 0; i < q; ++i) {
if (qAsk[i]) cout << ans[i] << "\n";
}
return 0;
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:170:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
170 | for (int i = 0; i < s.size(); ++i) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
860 KB |
Output is correct |
| 5 |
Correct |
1 ms |
860 KB |
Output is correct |
| 6 |
Correct |
1 ms |
860 KB |
Output is correct |
| 7 |
Correct |
1 ms |
860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1193 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
12124 KB |
Output is correct |
| 2 |
Correct |
15 ms |
12944 KB |
Output is correct |
| 3 |
Correct |
14 ms |
12636 KB |
Output is correct |
| 4 |
Correct |
9 ms |
10076 KB |
Output is correct |
| 5 |
Runtime error |
1719 ms |
524288 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
10328 KB |
Output is correct |
| 2 |
Correct |
12 ms |
11100 KB |
Output is correct |
| 3 |
Correct |
13 ms |
11520 KB |
Output is correct |
| 4 |
Correct |
15 ms |
11868 KB |
Output is correct |
| 5 |
Runtime error |
725 ms |
524288 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
860 KB |
Output is correct |
| 5 |
Correct |
1 ms |
860 KB |
Output is correct |
| 6 |
Correct |
1 ms |
860 KB |
Output is correct |
| 7 |
Correct |
1 ms |
860 KB |
Output is correct |
| 8 |
Runtime error |
1193 ms |
524288 KB |
Execution killed with signal 9 |
| 9 |
Halted |
0 ms |
0 KB |
- |
