#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using pii = pair<int,int>;
int n,q,cnt[300001],l[300001][2],r[300001][2],v[300001][2];
int ans[300001];
char str[300010];
set<pair<pii,int>> tr;
struct seg_tr{
int tr[300001];
void upd(int cur,int val) {
while(cur<=n) {
tr[cur] += val;
cur += cur & -cur;
}
}
int get(int cur) {
int ret=0;
while(cur) {
ret += tr[cur];
cur -= cur & -cur;
}
return ret;
}
}st;
void solve(int s,int f) {
if(s==f) return;
int md=(s+f)>>1;
solve(s,md);
solve(md+1,f);
vector<pair<pii,int>> ia,qa;
for(int i=s;i<=md;i++) if(cnt[i]) {
for(int j=0;j<cnt[i];j++) ia.push_back({pii(l[i][j],r[i][j]),v[i][j]});
}
for(int i=md+1;i<=f;i++) if(!cnt[i]) {
qa.push_back({pii(l[i][0],r[i][0]),i});
}
sort(ia.begin(),ia.end(),[](const pair<pii,int> &a, const pair<pii,int> &b) {
return a.fi.se > b.fi.se;
});
sort(qa.begin(),qa.end(),[](const pair<pii,int> &a, const pair<pii,int> &b) {
return a.fi.se > b.fi.se;
});
int i,j;
for(i=0,j=0;i<(int)qa.size();i++) {
for(;j<(int)ia.size() && ia[j].fi.se >= qa[i].fi.se; j++) st.upd(ia[j].fi.fi,ia[j].se);
ans[qa[i].se] += st.get(qa[i].fi.fi);
}
for(j=j-1;j>=0;j--) st.upd(ia[j].fi.fi,-ia[j].se);
}
int main() {
scanf("%d%d",&n,&q);
scanf("%s",str+1);
for(int i=1;i<=n;i++) str[i] -= '0';
for(int i=1,j=1;i<=n;i=j) {
if(!str[i]) {
j=i+1; continue;
}
for(j=i;j<=n && str[j];j++);
tr.insert({pii(i,j-1), 0});
}
char tmp[10];
int a,b;
for(int i=1;i<=q;i++) {
scanf("%s",tmp);
if(tmp[0] == 'q') {
scanf("%d%d",&a,&b);
b--;
l[i][0]=a; r[i][0]=b;
auto it = tr.upper_bound({pii(a,n+1),n+1});
if(it!=tr.begin()) {
it--;
if(it->fi.se >= b) ans[i] += i-it->se;
}
} else {
scanf("%d",&a);
str[a]^=1;
if(str[a]) {
int li=a,ri=a;
auto it = tr.lower_bound({pii(a,n), 0});
if(it!=tr.begin()) {
it--;
if(it->fi.se == li-1) {
tie(l[i][cnt[i]], r[i][cnt[i]]) = it->fi;
v[i][cnt[i]++] = i - it->se;
li = it->fi.fi;
it = tr.erase(it);
} else it++;
}
if(it!=tr.end()) {
if(it->fi.fi == ri+1) {
tie(l[i][cnt[i]], r[i][cnt[i]]) = it->fi;
v[i][cnt[i]++] = i - it->se;
ri = it->fi.se;
tr.erase(it);
}
}
tr.insert({pii(li,ri), i});
} else {
auto it = tr.upper_bound({pii(a,n+1),n+1});
it--;
tie(l[i][cnt[i]], r[i][cnt[i]]) = it->fi;
v[i][cnt[i]++] = it->se;
if(it->fi.fi != a) {
tr.insert({pii(it->fi.fi, a-1), i});
}
if(it->fi.se != a) {
tr.insert({pii(a+1, it->fi.se), i});
}
tr.erase(it);
}
}
}
solve(1,q);
for(int i=1;i<=q;i++) if(!cnt[i]) printf("%d\n",ans[i]);
return 0;
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&q);
~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",str+1);
~~~~~^~~~~~~~~~~~
street_lamps.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",tmp);
~~~~~^~~~~~~~~~
street_lamps.cpp:78:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a,&b);
~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:88:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a);
~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
424 ms |
16240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
380 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
