#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define f first
#define s second
int n,q;
int a[200005];
struct node;
extern node *emp;
struct node{
int mx=0,mn=0;
node *l,*r;
node(){l=r=this;mx=0;mn=0;}
node(int mmx,int mmn,node *ll=emp,node *rr=emp)
{
l=ll; r=rr;
mx=mmx;
mn=mmn;
}
};
node *emp = new node;
node *ins(node *rt,int nl,int nr,int ns=1,int ne=1e9)
{
if(ne<nl||nr<ns)
return rt;
if(nl<=ns&&ne<=nr)
{
return new node(1,1);
}
int mid=ns+(ne-ns)/2;
node *l=ins(rt->l,nl,nr,ns,mid);
node *r=ins(rt->r,nl,nr,mid+1,ne);
return new node(max({rt->mx,l->mx,r->mx}),max(rt->mn,min(l->mn,r->mn)),l,r);
}
int qry(node *rt,int nl,int nr,int ns=1,int ne=1e9)
{
//cout<<ns<<" "<<ne<<" "<<rt->mn<<" "<<rt->mx<<endl;
if(nr<ns||ne<nl)
return 0;
if(!rt->mx)
return 0;
if(nl<=ns&&ne<=nr&&rt->mn&&rt->mx)
return ne-ns+1;
int mid=ns+(ne-ns)/2;
return qry(rt->l,nl,nr,ns,mid)+qry(rt->r,nl,nr,mid+1,ne);
}
signed main()
{
//freopen("in.txt","r",stdin);
//freopen("out.out","w",stdout);
// cin.tie(0);cout.tie(0);
// ios_base::sync_with_stdio(0);
cin>>q;
int qt,l,r;
int lst=0;
node *rt=emp;
while(q--)
{
cin>>qt>>l>>r;
l+=lst;r+=lst;
if(qt==1)
{
int ans=qry(rt,l,r);
cout<<ans<<"\n";
lst=ans;
}
else
{
rt=ins(rt,l,r);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
