#include<iostream>
#include<bits/stdc++.h>
#define MAXN 4000010
#define BIL 1000000010
using namespace std;
struct node
{
int l,r;
int lazy;
void newNode()
{
lazy=0;
l=-1;
r=-1;
}
};
int len=1;
node tree[MAXN];
void update(int ind, int l, int r, int ql, int qr)
{
if(ql<=l && r<=qr)
{
tree[ind].lazy=1;
return;
}
int mid=(l+r)/2;
if(ql<=mid)
{
if(tree[ind].l==-1)
{
len++;
tree[len].newNode();
tree[len].lazy = tree[ind].lazy;
tree[ind].l=len;
}
update(tree[ind].l,l,mid,ql,qr);
}
if(qr>mid)
{
if(tree[ind].r==-1)
{
len++;
tree[len].newNode();
tree[len].lazy = tree[ind].lazy;
tree[ind].r=len;
}
update(tree[ind].r,mid+1,r,ql,qr);
}
//if(tree[tree[ind].l].lazy && tree[tree[ind].r].lazy)tree[ind].lazy=1;
}
int query(int ind, int l, int r, int ql, int qr)
{
if(r<ql || l>qr)return 0;
if(ql<=l && r<=qr && tree[ind].lazy==1)return r-l+1;
int mid=(l+r)/2;
int val1=0,val2=0;
if(ql<=mid)
{
if(tree[ind].l!=-1)val1= query(tree[ind].l,l,mid,ql,qr);
else if(tree[ind].lazy==1)
{
len++;
tree[len].newNode();
tree[len].lazy = tree[ind].lazy;
tree[ind].l=len;
tree[tree[ind].l].lazy=1;
val1= query(tree[ind].l,l,mid,ql,qr);
}
}
if(qr>mid)
{
if(tree[ind].r!=-1)val2= query(tree[ind].r,mid+1,r,ql,qr);
else if(tree[ind].lazy==1)
{
len++;
tree[len].newNode();
tree[len].lazy = tree[ind].lazy;
tree[ind].r=len;
tree[tree[ind].r].lazy=1;
val2= query(tree[ind].r,mid+1,r,ql,qr);
}
}
return val1+val2;
}
int main()
{
int n,c=0;
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n;
tree[1].newNode();
for(int i=0;i<n;i++)
{
int d,x,y;
cin>>d>>x>>y;
if(d==2)
{
update(1,1,BIL,x+c,y+c);
}
else
{
int res=query(1,1,BIL,x+c,y+c);
c=res;
cout<<res<<"\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
