/** * * * * * * * * * * * * * **\
* *
* Author: Haidara Nassour *
* Coded in: YYYY\M\D HH:MM:SS *
* Lang: C++ *
* *
\** * * * * * * * * * * * * * **/
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const int maxn=123456;
struct node
{
int sum,lazy,lc,rc,l,r;
node():sum(0),lazy(0),rc(-1),lc(-1),l(0),r(1e9) {}
} st[maxn*64];
int nodecnt=2;
void create(int inx,int child)
{
int mid=(st[inx].l+st[inx].r)/2;
if(child==1)
{
st[inx].lc=nodecnt++;
st[st[inx].lc].l=st[inx].l;
st[st[inx].lc].r=mid;
}
else
{
st[inx].rc=nodecnt++;
st[st[inx].rc].l=mid+1;
st[st[inx].rc].r=st[inx].r;
}
}
void pull(int inx)
{
if(st[inx].lazy)
{
st[inx].sum=st[inx].r-st[inx].l+1;
if(st[inx].l!=st[inx].r)
{
int mid=(st[inx].l+st[inx].r)/2;
if(st[inx].lc==-1)
create(inx,1);
if(st[inx].rc==-1)
create(inx,2);
st[st[inx].lc].lazy=1;
st[st[inx].rc].lazy=1;
}
}
st[inx].lazy=0;
}
int push_up(int inx)
{
int res1=st[st[inx].lc].sum;
int res2=st[st[inx].rc].sum;
if(st[st[inx].lc].lazy)
res1=(st[inx].l+st[inx].r)/2-st[inx].l+1;
if(st[st[inx].rc].lazy)
res2=st[inx].r-(st[inx].l+st[inx].r)/2;
return res1+res2;
}
void update(int ul,int ur,int inx)
{
pull(inx);
if(ul==st[inx].l&&st[inx].r==ur)
{
st[inx].lazy=1;
pull(inx);
return ;
}
int mid=(st[inx].l+st[inx].r)/2;
if(st[inx].lc==-1)
create(inx,1);
if(st[inx].rc==-1)
create(inx,2);
if(ul>mid)
update(ul,ur,st[inx].rc);
else if(ur<mid+1)
update(ul,ur,st[inx].lc);
else
{
update(ul,mid,st[inx].lc);
update(mid+1,ur,st[inx].rc);
}
st[inx].sum=push_up(inx);
}
int query(int ql,int qr,int inx)
{
pull(inx);
if(ql==st[inx].l&&st[inx].r==qr)
return st[inx].sum;
int mid=(st[inx].l+st[inx].r)/2;
if(st[inx].lc==-1)
create(inx,1);
if(st[inx].rc==-1)
create(inx,2);
int res=0;
if(ql>mid)
res=query(ql,qr,st[inx].rc);
else if(qr<mid+1)
res=query(ql,qr,st[inx].lc);
else
res=query(ql,mid,st[inx].lc)+query(mid+1,qr,st[inx].rc);
st[inx].sum=push_up(inx);
return res;
}
signed main()
{
int q;
cin>>q;
int c=0;
while(q--)
{
int t;
cin>>t;
if(t==1)
{
int j,k;
cin>>j>>k;
c=query(j+c,k+c,1);
cout<<c<<endl;
}
else
{
int j,k;
cin>>j>>k;
update(j+c,k+c,1);
}
}
}
Compilation message
apple.cpp: In constructor 'node::node()':
apple.cpp:14:21: warning: 'node::rc' will be initialized after [-Wreorder]
14 | int sum,lazy,lc,rc,l,r;
| ^~
apple.cpp:14:18: warning: 'int node::lc' [-Wreorder]
14 | int sum,lazy,lc,rc,l,r;
| ^~
apple.cpp:15:5: warning: when initialized here [-Wreorder]
15 | node():sum(0),lazy(0),rc(-1),lc(-1),l(0),r(1e9) {}
| ^~~~
apple.cpp: In function 'void pull(int)':
apple.cpp:41:17: warning: unused variable 'mid' [-Wunused-variable]
41 | int mid=(st[inx].l+st[inx].r)/2;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
185704 KB |
Output is correct |
| 2 |
Correct |
89 ms |
185720 KB |
Output is correct |
| 3 |
Correct |
89 ms |
185748 KB |
Output is correct |
| 4 |
Correct |
114 ms |
185784 KB |
Output is correct |
| 5 |
Correct |
121 ms |
185768 KB |
Output is correct |
| 6 |
Correct |
119 ms |
185832 KB |
Output is correct |
| 7 |
Correct |
119 ms |
185924 KB |
Output is correct |
| 8 |
Correct |
284 ms |
185956 KB |
Output is correct |
| 9 |
Correct |
496 ms |
186168 KB |
Output is correct |
| 10 |
Correct |
508 ms |
186156 KB |
Output is correct |
| 11 |
Correct |
500 ms |
186264 KB |
Output is correct |
| 12 |
Correct |
509 ms |
186132 KB |
Output is correct |
| 13 |
Correct |
480 ms |
186308 KB |
Output is correct |
| 14 |
Correct |
494 ms |
186300 KB |
Output is correct |
| 15 |
Correct |
583 ms |
186624 KB |
Output is correct |
| 16 |
Correct |
579 ms |
186564 KB |
Output is correct |
| 17 |
Correct |
501 ms |
186692 KB |
Output is correct |
| 18 |
Correct |
502 ms |
186844 KB |
Output is correct |
| 19 |
Correct |
586 ms |
186632 KB |
Output is correct |
| 20 |
Correct |
584 ms |
186576 KB |
Output is correct |
