#include<bits/stdc++.h>
#define ll long long
#define ljc 998244353
using namespace std;
#define gc getchar
inline ll read(){
register ll x=0,f=1;char ch=gc();
while (!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while (isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=gc();}
return (f==1)?x:-x;
}
int n,N,T,root[600001],cnt;
struct node{
int l,r,sum;
}seg[15020001];
#define mid ((lb+rb)>>1)
void Update(int &rt,int lb,int rb,int pos,int w){
if (!rt) rt=++cnt;seg[rt].sum+=w;
if (lb==rb) return;
(mid>=pos?Update(seg[rt].l,lb,mid,pos,w):Update(seg[rt].r,mid+1,rb,pos,w));
}
int Query(int rt,int lb,int rb,int l,int r){
if (!rt||lb>r||rb<l) return 0;
if (lb>=l&&rb<=r) return seg[rt].sum;
return Query(seg[rt].l,lb,mid,l,r)+Query(seg[rt].r,mid+1,rb,l,r);
}
inline void update(int pos,int r,int w){
for (;pos<=n+1;pos+=pos&-pos) Update(root[pos],1,n+1,r,w);
}
inline int query(int posx,int posy){
int ans=0;
for (;posx;posx-=posx&-posx) ans+=Query(root[posx],1,n+1,1,posy);
return ans;
}
inline void Add(int x1,int y1,int x2,int y2,int W){
update(x1,y1,W);update(x1,y2+1,-W);
update(x2+1,y1,-W);update(x2+1,y2+1,W);
}
struct road{
int l,r;
};
inline bool operator < (road a,road b){
return a.r<b.r;
}
set<road> S;
set<road>::iterator it;
bool zt[2000001];
signed main(){
n=1+read(),T=read();N=n-1;
for (int i=1;i<=n;i++){
S.insert((road){i,i});
}
for (int i=1;i<=N;i++){
char ch=gc();
while (!isdigit(ch)) ch=gc();
zt[i]=(ch-48);
if (zt[i]){
it=S.lower_bound((road){0,i+1});it--;
int lb=(*it).l;
S.erase(it);S.erase((road){i+1,i+1});
S.insert((road){lb,i+1});
}
}
for (it=S.begin();it!=S.end();++it){
Add((*it).l,(*it).l,(*it).r,(*it).r,T);
}
for (int t=1;t<=T;t++){
char s[11];scanf("%s",s+1);
if (s[1]=='q'){
int x=read(),y=read();
int ans=query(x,y);
int X=(*(S.lower_bound((road){0,x}))).l;
int Y=(*(S.lower_bound((road){0,y}))).l;
printf("%d\n",ans-(T-t)*(X==Y));
}else if (s[1]=='t'){
int x=read();
if (zt[x]==1){
it=S.lower_bound((road){0,x});
int lb1=(*it).l,rb1=x;
int lb2=x+1,rb2=(*it).r;
Add(lb1,lb2,rb1,rb2,t-T);
S.erase((road){lb1,rb2});
S.insert((road){lb1,rb1});S.insert((road){lb2,rb2});
zt[x]^=1;
}else{
it=S.lower_bound((road){0,x});
int lb1=(*it).l,rb1=x;
it++;
int lb2=x+1,rb2=(*it).r;
Add(lb1,lb2,rb1,rb2,T-t);
S.erase((road){lb1,rb1});S.erase((road){lb2,rb2});
S.insert((road){lb1,rb2});
zt[x]^=1;
}
}
}
return 0;
}
Compilation message
street_lamps.cpp: In function 'long long int read()':
street_lamps.cpp:7:17: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
7 | register ll x=0,f=1;char ch=gc();
| ^
street_lamps.cpp:7:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
7 | register ll x=0,f=1;char ch=gc();
| ^
street_lamps.cpp: In function 'void Update(int&, int, int, int, int)':
street_lamps.cpp:18:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
18 | if (!rt) rt=++cnt;seg[rt].sum+=w;
| ^~
street_lamps.cpp:18:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
18 | if (!rt) rt=++cnt;seg[rt].sum+=w;
| ^~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:68:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | char s[11];scanf("%s",s+1);
| ~~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
312 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
241 ms |
1248 KB |
Output is correct |
2 |
Correct |
329 ms |
4980 KB |
Output is correct |
3 |
Correct |
639 ms |
8084 KB |
Output is correct |
4 |
Correct |
2495 ms |
146668 KB |
Output is correct |
5 |
Correct |
2184 ms |
124028 KB |
Output is correct |
6 |
Correct |
2619 ms |
149960 KB |
Output is correct |
7 |
Correct |
2495 ms |
166256 KB |
Output is correct |
8 |
Correct |
217 ms |
22588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
596 KB |
Output is correct |
2 |
Correct |
4 ms |
596 KB |
Output is correct |
3 |
Correct |
3 ms |
588 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
3917 ms |
183308 KB |
Output is correct |
6 |
Correct |
2966 ms |
158676 KB |
Output is correct |
7 |
Correct |
1977 ms |
123372 KB |
Output is correct |
8 |
Correct |
227 ms |
22552 KB |
Output is correct |
9 |
Correct |
66 ms |
3980 KB |
Output is correct |
10 |
Correct |
71 ms |
4236 KB |
Output is correct |
11 |
Correct |
72 ms |
4504 KB |
Output is correct |
12 |
Correct |
2067 ms |
166296 KB |
Output is correct |
13 |
Correct |
218 ms |
22652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
3 ms |
584 KB |
Output is correct |
3 |
Correct |
4 ms |
596 KB |
Output is correct |
4 |
Correct |
4 ms |
576 KB |
Output is correct |
5 |
Correct |
1421 ms |
123368 KB |
Output is correct |
6 |
Correct |
1925 ms |
138740 KB |
Output is correct |
7 |
Correct |
2534 ms |
149476 KB |
Output is correct |
8 |
Correct |
3262 ms |
159064 KB |
Output is correct |
9 |
Correct |
385 ms |
4056 KB |
Output is correct |
10 |
Correct |
323 ms |
3284 KB |
Output is correct |
11 |
Correct |
380 ms |
3968 KB |
Output is correct |
12 |
Correct |
319 ms |
3276 KB |
Output is correct |
13 |
Correct |
374 ms |
4204 KB |
Output is correct |
14 |
Correct |
325 ms |
3400 KB |
Output is correct |
15 |
Correct |
2082 ms |
166104 KB |
Output is correct |
16 |
Correct |
215 ms |
22604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
312 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
241 ms |
1248 KB |
Output is correct |
9 |
Correct |
329 ms |
4980 KB |
Output is correct |
10 |
Correct |
639 ms |
8084 KB |
Output is correct |
11 |
Correct |
2495 ms |
146668 KB |
Output is correct |
12 |
Correct |
2184 ms |
124028 KB |
Output is correct |
13 |
Correct |
2619 ms |
149960 KB |
Output is correct |
14 |
Correct |
2495 ms |
166256 KB |
Output is correct |
15 |
Correct |
217 ms |
22588 KB |
Output is correct |
16 |
Correct |
5 ms |
596 KB |
Output is correct |
17 |
Correct |
4 ms |
596 KB |
Output is correct |
18 |
Correct |
3 ms |
588 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
3917 ms |
183308 KB |
Output is correct |
21 |
Correct |
2966 ms |
158676 KB |
Output is correct |
22 |
Correct |
1977 ms |
123372 KB |
Output is correct |
23 |
Correct |
227 ms |
22552 KB |
Output is correct |
24 |
Correct |
66 ms |
3980 KB |
Output is correct |
25 |
Correct |
71 ms |
4236 KB |
Output is correct |
26 |
Correct |
72 ms |
4504 KB |
Output is correct |
27 |
Correct |
2067 ms |
166296 KB |
Output is correct |
28 |
Correct |
218 ms |
22652 KB |
Output is correct |
29 |
Correct |
2 ms |
468 KB |
Output is correct |
30 |
Correct |
3 ms |
584 KB |
Output is correct |
31 |
Correct |
4 ms |
596 KB |
Output is correct |
32 |
Correct |
4 ms |
576 KB |
Output is correct |
33 |
Correct |
1421 ms |
123368 KB |
Output is correct |
34 |
Correct |
1925 ms |
138740 KB |
Output is correct |
35 |
Correct |
2534 ms |
149476 KB |
Output is correct |
36 |
Correct |
3262 ms |
159064 KB |
Output is correct |
37 |
Correct |
385 ms |
4056 KB |
Output is correct |
38 |
Correct |
323 ms |
3284 KB |
Output is correct |
39 |
Correct |
380 ms |
3968 KB |
Output is correct |
40 |
Correct |
319 ms |
3276 KB |
Output is correct |
41 |
Correct |
374 ms |
4204 KB |
Output is correct |
42 |
Correct |
325 ms |
3400 KB |
Output is correct |
43 |
Correct |
2082 ms |
166104 KB |
Output is correct |
44 |
Correct |
215 ms |
22604 KB |
Output is correct |
45 |
Correct |
82 ms |
2676 KB |
Output is correct |
46 |
Correct |
148 ms |
2676 KB |
Output is correct |
47 |
Correct |
1051 ms |
51292 KB |
Output is correct |
48 |
Correct |
2448 ms |
146340 KB |
Output is correct |
49 |
Correct |
77 ms |
4428 KB |
Output is correct |
50 |
Correct |
79 ms |
4308 KB |
Output is correct |
51 |
Correct |
76 ms |
4560 KB |
Output is correct |
52 |
Correct |
81 ms |
4888 KB |
Output is correct |
53 |
Correct |
87 ms |
5000 KB |
Output is correct |
54 |
Correct |
78 ms |
4912 KB |
Output is correct |