#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const ll maxn =1e9;
int m;
struct Node
{
int cntr=0;
bool lazy=0;
int l,r;
Node *left=nullptr;
Node *right=nullptr;
};
Node *root;
void extendleft(Node *node)
{
if(node->left==nullptr && node->l!=node->r)
{
int mid=(node->l+node->r)/2;
node->left=new Node();
node->left->l=node->l;
node->left->r=mid;
node->left->lazy=node->lazy;
}
}
void extendright(Node *node)
{
if(node->right==nullptr && node->l!=node->r)
{
int mid=(node->l+node->r)/2;
node->right=new Node();
node->right->l=mid+1;
node->right->r=node->r;
node->right->lazy=node->lazy;
}
}
void extend(Node *node)
{
extendleft(node);
extendright(node);
// printf("out of extend\n");
}
void pushLazy(Node *node)
{
if(node->lazy)
{
node->cntr=node->r-node->l+1;
extend(node);
if(node->l!=node->r)
{
node->left->lazy=1;
node->right->lazy=1;
}
node->lazy=0;
}
}
void update(int ul,int ur,Node *node)
{
// printf("in update %d %d\n",node->l,node->r);
pushLazy(node);
if(ur<node->l || node->r<ul) return;
//pushLazy(node);
if(ul<=node->l && node->r<=ur)
{
// printf("doing hole with %d %d\n",node->l,node->r);
node->cntr=node->r-node->l+1;
extend(node);
if(node->l!=node->r)
{
node->left->lazy=1;
node->right->lazy=1;
}
// printf("finishing whole %d %d\n",node->l,node->r);
return;
}
int mid=(node->l+node->r)/2;
if(ul<=mid) extendleft(node);
if(ur>mid) extendright(node);
if(node->left!=nullptr) update(ul,ur,node->left);
if(node->right!=nullptr) update(ul,ur,node->right);
node->cntr=0;
if(node->left!=nullptr) node->cntr+=node->left->cntr;
if(node->right!=nullptr) node->cntr+=node->right->cntr;
}
int query(int ql,int qr,Node *node)
{
pushLazy(node);
if(qr<node->l || node->r<ql) return 0;
//pushLazy(node);
if(ql<=node->l && node->r<=qr)
{
return node->cntr;
}
int mid=(node->l+node->r)/2;
if(ql<=mid) extendleft(node);
if(qr>mid) extendright(node);
int ans=0;
if(node->left!=nullptr) ans+=query(ql,qr,node->left);
if(node->right!=nullptr) ans+=query(ql,qr,node->right);
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>m;
root=new Node();
root->l=1;
root->r=maxn;
ll c=0;
for(int i=0;i<m;i++)
{
// printf("in query %d\n",i);
int t,x,y;
cin>>t>>x>>y;
if(t==1)
{
c=query(x+c,y+c,root);
cout<<c<<"\n";
}
if(t==2)
{
update(x+c,y+c,root);
}
}
}
/*
3
2 5 8
2 7 10
1 1 10
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |