#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 BIT{
int n;
vector<ll> sm;
BIT(int _n){
n = _n;
sm.resize(n);
}
void upd(int in, int x){
in++;
while(in <= n) sm[in-1]+=x, in+=in&-in;
}
ll sum(int in){
in++;
ll s = 0;
while(in >= 1) s+=sm[in-1], in-=in&-in;
return s;
}
ll sum(int l, int r){
return sum(r)-(l == 0? 0:sum(l-1));
}
};
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(r, l) < make_pair(a.r, a.l);
}
};
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 = 1; tt <= tg.size(); tt++){
int in = tg[tt-1];
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);
}
if(in+1 < n && seg.get(in+1) == 1){
int r = seg.find(in+1);
seg_add(in+1, r, tt);
}
}
}
//for(auto sg: segments) cerr << sg.l << " " << sg.r << " " << sg.init << " " << sg.closed << " d\n";
vector<vector<int>> sg2(n);
for(int i = 0; i < segments.size(); i++){
if(segments[i].closed) continue;
sg2[segments[i].l].pb(segments[i].r);
segments[i].close(tg.size());
}
vector<vector<segment>> rrs(n);
vector<vector<tuple<int, int, int>>> rrq(n);
for(int i = 0; i < segments.size(); i++){
rrs[segments[i].l].pb(segments[i]);
}
for(int i = 0; i < query.size(); i++) rrq[get<0>(query[i])].pb(query[i]);
BIT bit(n);
vector<ll> ans(query.size(), 0);
for(int i = 0; i < n; i++){
for(auto sg: rrs[i]) bit.upd(sg.r, sg.vl);
for(auto [a, b, in]: rrq[i]) ans[in]+=bit.sum(b, n-1);
}
bit = BIT(n);
for(int i = 0; i < n; i++){
for(int r: sg2[i]) bit.upd(r, 1);
for(auto [a, b, in]: rrq[i]) ans[in]+=bit.sum(b, n-1)*in;
}
for(ll x: ans) cout << x << "\n";
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:137:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for(int tt = 1; tt <= tg.size(); tt++){
| ~~~^~~~~~~~~~~~
street_lamps.cpp:168:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<main()::segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
168 | for(int i = 0; i < segments.size(); i++){
| ~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:175:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<main()::segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
175 | for(int i = 0; i < segments.size(); i++){
| ~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:178:22: 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]
178 | for(int i = 0; i < query.size(); i++) rrq[get<0>(query[i])].pb(query[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 |
Incorrect |
184 ms |
14076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
460 KB |
Output is correct |
| 2 |
Correct |
2 ms |
460 KB |
Output is correct |
| 3 |
Correct |
2 ms |
460 KB |
Output is correct |
| 4 |
Correct |
2 ms |
460 KB |
Output is correct |
| 5 |
Correct |
351 ms |
54244 KB |
Output is correct |
| 6 |
Correct |
568 ms |
63464 KB |
Output is correct |
| 7 |
Correct |
658 ms |
68580 KB |
Output is correct |
| 8 |
Correct |
943 ms |
74336 KB |
Output is correct |
| 9 |
Correct |
261 ms |
18992 KB |
Output is correct |
| 10 |
Correct |
247 ms |
18136 KB |
Output is correct |
| 11 |
Correct |
263 ms |
19040 KB |
Output is correct |
| 12 |
Correct |
248 ms |
18120 KB |
Output is correct |
| 13 |
Correct |
303 ms |
19032 KB |
Output is correct |
| 14 |
Correct |
252 ms |
17932 KB |
Output is correct |
| 15 |
Correct |
281 ms |
46476 KB |
Output is correct |
| 16 |
Correct |
295 ms |
47952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
