#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll m,i,x,y,d,c,ans;
struct node{
node *le,*ri;
ll val,lazy,l,r;
};
void fix(node *s){
if(s->l==s->r){
if(s->lazy==1) s->val=1;
return;
}
ll mid=(s->l+s->r)/2;
if(s->le==NULL){
s->le=new node;
s->le->le=NULL;
s->le->ri=NULL;
s->le->l=s->l;
s->le->r=mid;
s->le->lazy=0;
s->le->val=0;
}
if(s->ri==NULL){
s->ri=new node;
s->ri->le=NULL;
s->ri->ri=NULL;
s->ri->l=mid+1;
s->ri->r=s->r;
s->ri->lazy=0;
s->ri->val=0;
}
if(s->lazy==1){
s->val=s->r-s->l+1;
s->le->lazy=1;
s->ri->lazy=1;
s->lazy=0;
}
}
ll query(node *s,ll x,ll y){
fix(s);
if(s->l>y || s->r<x) return 0;
if(s->l>=x && s->r<=y) return s->val;
return query(s->le,x,y)+query(s->ri,x,y);
}
void update(node *s,ll x,ll y){
fix(s);
if(s->l>y || s->r<x) return;
if(s->l>=x && s->r<=y){
s->val=s->r-s->l+1;
if(s->l!=s->r){
s->le->lazy=1;
s->ri->lazy=1;
}
return;
}
update(s->le,x,y);
update(s->ri,x,y);
s->val=s->le->val+s->ri->val;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> m;
node *s = new node;
s->le=NULL;
s->ri=NULL;
s->val=0;
s->lazy=0;
s->l=1;
s->r=1e9;
for(i=1;i<=m;i++){
cin >> d >> x >> y;
if(d==1){
ans=query(s,x+c,y+c);
cout << ans << "\n";
c=ans;
}
else{
update(s,x+c,y+c);
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
15 ms |
11612 KB |
Output is correct |
5 |
Correct |
19 ms |
14028 KB |
Output is correct |
6 |
Correct |
19 ms |
13396 KB |
Output is correct |
7 |
Correct |
19 ms |
13916 KB |
Output is correct |
8 |
Correct |
174 ms |
103308 KB |
Output is correct |
9 |
Correct |
320 ms |
176084 KB |
Output is correct |
10 |
Correct |
334 ms |
197444 KB |
Output is correct |
11 |
Correct |
354 ms |
214024 KB |
Output is correct |
12 |
Correct |
360 ms |
221344 KB |
Output is correct |
13 |
Runtime error |
331 ms |
262144 KB |
Execution killed with signal 9 |
14 |
Halted |
0 ms |
0 KB |
- |