#include <bits/stdc++.h>
using namespace std;
struct BIT{
int qry(int x, int y){
return 0;
}
} bit;
struct segment{
int l, r, t;
bool operator< (const segment& o) const {
return l < o.l || l == o.l && r < o.r;
}
void add(int t2) const {
// cout << "ADD " << l << ' ' << r << ' ' << t << ' ' << t2 << endl;
}
};
set<segment> S;
bool on[300002];
void show(){
for(auto i : S) cout << '[' << i.l << ", " << i.r << ']' << ' '; cout << '\n';
}
void toggle(int x, int t){
// cout << "TOGGLE " << x << ' ' << t << endl;
if(on[x]){
auto ptr = S.lower_bound({x, 1 << 30}); --ptr; int l = ptr->l, r = ptr->r; S.erase(ptr);
if(on[x - 1]) { S.insert({l, x, t}); }
if(on[x + 1]) { S.insert({x + 1, r, t}); }
}else{
int l = x, r = x + 1;
if(on[x - 1]) { auto ptr = S.lower_bound({x, -1}); --ptr; l = ptr->l; ptr->add(t); S.erase(ptr); }
if(on[x + 1]) { auto ptr = S.lower_bound({x, -1}); r = ptr->r; ptr->add(t); S.erase(ptr); }
S.insert({l, r, t});
}
on[x] = !on[x];
// show();
}
int query(int l, int r, int t){
// cout << "QUERY " << l << ' ' << r << ' ' << t << endl;
int ans = bit.qry(r, r) - bit.qry(l, r) - bit.qry(l, l) + bit.qry(r, r);
auto ptr = S.lower_bound({l, 1 << 30});
if(ptr != S.begin() && prev(ptr)->l <= l && r <= prev(ptr)->r) ans += t - prev(ptr)->t;
return ans;
}
int32_t main(){
int n, q; cin >> n >> q;
string s; cin >> s; for(int i = 1; i <= n; i++) on[i] = s[i - 1] == '1';
vector<segment> v;
for(int i = 1; i <= n; i++) {
if(on[i]){
if(v.size() && v.back().r == i) v.back().r++; else v.push_back({i, i + 1, 0});
}
}
for(auto s : v) S.insert(s);
for(int t = 1; t <= q; t++){
string type; cin >> type;
if(type == "query"){
int l, r; cin >> l >> r;
cout << query(l, r, t) << endl;
}else{
int x; cin >> x; toggle(x, t);
}
}
}
Compilation message
street_lamps.cpp: In member function 'bool segment::operator<(const segment&) const':
street_lamps.cpp:15:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
15 | return l < o.l || l == o.l && r < o.r;
| ~~~~~~~~~^~~~~~~~~~
street_lamps.cpp: In function 'void show()':
street_lamps.cpp:26:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
26 | for(auto i : S) cout << '[' << i.l << ", " << i.r << ']' << ' '; cout << '\n';
| ^~~
street_lamps.cpp:26:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
26 | for(auto i : S) cout << '[' << i.l << ", " << i.r << ']' << ' '; cout << '\n';
| ^~~~
| # |
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 |
461 ms |
644 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 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 3 |
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 |
- |
