#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
struct segtree{
int k, n;
vector<int> mn;
segtree(int _n){
n = _n;
k = 1;
while(k < n) k*=2;
k*=2;
mn.resize(k, 1);
}
void toggle(int in){
in+=k/2;
mn[in] = !mn[in];
in/=2;
while(in > 0){
mn[in] = min(mn[2*in], mn[2*in+1]);
in/=2;
}
}
int get(int in){
return mn[in+k/2];
}
int find(int in, int nd, int a, int b){
if(mn[nd] == 1) return -1;
if(in > b) return -1;
if(a == b) return a;
int md = (a+b)/2;
int x;
return (x = find(in, 2*nd, a, md)) == -1 ? find(in, 2*nd+1, md+1, b) : x;
}
int find(int in){
int x = find(in, 1, 0, k/2-1);
if(x == -1) x = n;
x--;
return x;
}
int rfind(int in, int nd, int a, int b){
if(mn[nd] == 1) return -1;
if(in < a) return -1;
if(a == b) return a;
int md = (a+b)/2;
int x;
return (x = rfind(in, 2*nd+1, md+1, b)) == -1 ? rfind(in, 2*nd, a, md) : x;
}
int rfind(int in){
int x = rfind(in, 1, 0, k/2-1);
x++;
return x;
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, q; cin >> n >> q;
segtree seg(n);
for(int i = 0; i < n; i++){
char c; cin >> c;
if(c == '0') seg.toggle(i);
}
vector<int> tg;
vector<tuple<int, int, int>> query;
for(int i = 0; i < q; i++){
str tt; cin >> tt;
if(tt == "toggle"){
int in; cin >> in; in--;
tg.pb(in);
}
else{
int a, b; cin >> a >> b; a--, b-=2;
query.pb({a, b, query.size()});
}
}
map<pair<int, int>, int> mp;
struct segment{
int l, r, init, vl;
bool closed;
segment(int _l, int _r, int _init){
l = _l, r = _r, init = _init, vl = -1, closed = 0;
}
void close(int e){
vl = e-init+1;
closed = 1;
}
bool operator<(segment a){
return make_pair(l, r) < make_pair(a.l, a.r);
}
};
vector<segment> segments;
auto seg_add = [&](int l, int r, int init){
mp[{l, r}] = segments.size();
segments.pb(segment(l, r, init));
};
auto seg_rem = [&](int l, int r, int tt){
int pos = mp[{l, r}];
mp[{l, r}] = -1;
segments[pos].close(tt);
};
int sss = -1, eee = 0;
for(int i = 0; i < n; i++){
if(seg.get(i) == 0){
sss = -1;
continue;
}
if(sss == -1) sss = i, eee = i-1;
eee++;
if(i != n-1 && seg.get(i+1) == 1) continue;
seg_add(sss, eee, 0);
}
for(int tt = 0; tt < tg.size(); tt++){
int in = tg[tt];
if(seg.get(in) == 0){
if(in > 0 && seg.get(in-1) == 1){
int l = seg.rfind(in-1);
seg_rem(l, in-1, tt-1);
}
if(in+1 < n && seg.get(in+1) == 1){
int r = seg.find(in+1);
seg_rem(in+1, r, tt-1);
}
seg.toggle(in);
int l = seg.rfind(in), r = seg.find(in);
seg_add(l, r, tt);
}
else{
int l = seg.rfind(in), r = seg.find(in);
seg_rem(l, r, tt-1);
seg.toggle(in);
if(in > 0 && seg.get(in-1) == 1){
int l = seg.rfind(in-1);
seg_add(l, in-1, tt-1);
}
if(in+1 < n && seg.get(in+1) == 1){
int r = seg.find(in+1);
seg_add(in+1, r, tt-1);
}
}
}
vector<int> ans(query.size());
for(int qq = 0; qq < query.size(); qq++){
auto [a, b, in] = query[qq];
ans[in] = 0;
for(int i = 0; i < segments.size(); i++){
if(!(a >= segments[i].l && b <= segments[i].r)) continue;
if(segments[i].closed) ans[in]+=segments[i].vl;
else ans[in]+=(int)(tg.size())+qq-segments[i].init+1;
}
}
for(int x: ans) cout << x << "\n";
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:116:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(int tt = 0; tt < tg.size(); tt++){
| ~~~^~~~~~~~~~~
street_lamps.cpp:146:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for(int qq = 0; qq < query.size(); qq++){
| ~~~^~~~~~~~~~~~~~
street_lamps.cpp:149:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<main()::segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for(int i = 0; i < segments.size(); i++){
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5053 ms |
10700 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
324 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
