#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;
int R, C;
struct dty {
dty *l, *r;
int dt, L, R; int Key;
int md;
dty(int k) {Key=k; dt=0; l=r=NULL;}
inline void upd(int y, int val, int ys, int ye) {
md=(ys+ye)/2;
if (Key) {
if (Key==y) {dt+=val; return ;}
if (Key<=md) { l=new dty(Key); l->dt=dt; }
else { r=new dty(Key); r->dt=dt; }
Key=0;
}
if (y<=md) {
if (!l) l=new dty(y);
l->upd(y, val, ys, md);
}
else {
if (!r) r=new dty(y);
r->upd(y, val, md+1, ye);
}
L=(l?l->dt:0);
R=(r?r->dt:0);
dt+=L+R;
}
inline int get(int y1, int y2, int ys, int ye) {
md=(ys+ye)/2;
if (Key) return (y1<=Key&&Key<=y2)?dt:0;
if (y1<=ys&&ye<=y2) return dt;
L=R=0;
if (!(md<y1)) L=(l?(l->get(y1, y2, ys, md)):0);
if (md+1<=y2&&md+1<=ye) R=(r?r->get(y1, y2, md+1, ye):0);
return L+R;
}
inline int get(int y, int ys, int ye) {
md=(ys+ye)/2;
if (Key) return (y==Key?dt:0);
if (y<=md) return l?l->get(y, ys, md):0;
else return r?r->get(y, md+1, ye):0;
}
};
struct dtx {
dty *seg;
dtx *l, *r;
int md;
int L, R;
dtx() {l=r=NULL; seg=NULL;}
inline void upd(int x, int y, int val, int xs, int xe) {
if (!seg) seg=new dty(y);
if (xs==xe) {seg->upd(y, val, 1, C); return ;}
md=(xs+xe)/2;
if (x<=md) {
if (!l) l=new dtx();
l->upd(x, y, val, xs, md);
}
else {
if (!r) r=new dtx();
r->upd(x, y, val, md+1, xe);
}
seg->upd(y, val, 1, C);
}
inline int get(int x1, int y1, int x2, int y2, int xs, int xe) {
if (!seg) return 0;
if (x1<=xs&&xe<=x2) return seg->get(y1, y2, 1, C);
md=(xs+xe)/2;
L=R=0;
if (x1<=md) L=(l?(l->get(x1, y1, x2, y2, xs, md)):0);
if (md+1<=x2&&md+1<=xe) R=(r?(r->get(x1, y1, x2, y2, md+1, xe)):0);
return L+R;
}
};
dtx *root=new dtx();
int n, q;
char s[10]; int I, a, b;
int ar[300010];
set<pair<pii, int> > S;
int main() {
scanf("%d %d", &n, &q);
R=C=n;
for (int i=1; i<=n; i++) scanf("%1d", &ar[i]);
for (int i=1; i<=n; i++) {
if (!ar[i]) continue;
int j;
for (j=i; j<=n; j++) if (!ar[j]) break;
S.insert({make_pair(i, j-1), 0});
i=j-1;
}
set<pair<pii, int> >::iterator it;
pair<pii, int> pi, pi1, pi2;
int ans;
for (int i=1; i<=q; i++) {
scanf("%s", s);
if (s[0]=='t') {
scanf("%d", &I);
if (ar[I]) {
it=S.upper_bound({make_pair(I, (1<<30)), (1<<30)});
it--; pi=(*it); S.erase(it);
root->upd(pi.fi.fi, pi.fi.se, i-pi.se, 1, R);
if (pi.fi.fi<I) S.insert({make_pair(pi.fi.fi, I-1), i});
if (pi.fi.se>I) S.insert({make_pair(I+1, pi.fi.se), i});
}
else {
if (ar[I-1]) {
it=S.upper_bound({make_pair(I-1, (1<<30)), (1<<30)});
it--; pi1=(*it); S.erase(it);
root->upd(pi1.fi.fi, pi1.fi.se, i-pi1.se, 1, R);
}
else pi1={make_pair(I, I), 0};
if (ar[I+1]) {
it=S.upper_bound({make_pair(I+1, (1<<30)), (1<<30)});
it--; pi2=(*it); S.erase(it);
root->upd(pi2.fi.fi, pi2.fi.se, i-pi2.se, 1, R);
}
else pi2={make_pair(I, I), 0};
S.insert({make_pair(pi1.fi.fi, pi2.fi.se), i});
}
ar[I]=1-ar[I];
}
else {
scanf("%d %d", &a, &b); b--;
if (!S.size()) ans=0;
else {
it=S.upper_bound({make_pair(a, (1<<30)), (1<<30)});
if (it==S.begin()) ans=0;
else {
it--;
if ((*it).fi.fi<=a&&(*it).fi.se>=b) ans=i-(*it).se;
else ans=0;
}
}
ans+=root->get(1, b, a, C, 1, R);
printf("%d\n", ans);
}
}
return 0;
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:96:7: 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:98:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i=1; i<=n; i++) scanf("%1d", &ar[i]);
~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", s);
~~~~~^~~~~~~~~
street_lamps.cpp:112:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &I);
~~~~~^~~~~~~~~~
street_lamps.cpp:138:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b); b--;
~~~~~^~~~~~~~~~~~~~~~~
| # |
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 |
303 ms |
5360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1272 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1272 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
1016 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
6 ms |
760 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1016 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1272 KB |
Output is correct |
| 5 |
Correct |
581 ms |
21916 KB |
Output is correct |
| 6 |
Correct |
2003 ms |
227740 KB |
Output is correct |
| 7 |
Correct |
3269 ms |
376296 KB |
Output is correct |
| 8 |
Correct |
4860 ms |
519312 KB |
Output is correct |
| 9 |
Incorrect |
461 ms |
5372 KB |
Output isn't correct |
| 10 |
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 |
- |
