Submission #998404

#TimeUsernameProblemLanguageResultExecution timeMemory
998404amirhoseinfar1385Monkey and Apple-trees (IZhO12_apple)C++17
100 / 100
60 ms3112 KiB
#include<bits/stdc++.h>
using namespace std;
int c;
struct node{
	node *cl,*cr;
	int res=0,f=0;
	node(){
		cl=cr=NULL;
		res=f=0;
	}
}rishe;

node* getl(node *u){
	if((*u).cl==NULL){
		(*u).cl=new node();
	}
	return (*u).cl;
}

node* getr(node *u){
	if((*u).cr==NULL){
		(*u).cr=new node();
	}
	return (*u).cr;
}

void upd(node *u,int l,int r,int tl,int tr){
	if(l>r||l>tr||r<tl||tl>tr||(*u).f==1){
		return ;
	}
	if(l>=tl&&r<=tr){
		(*u).cl=(*u).cr=NULL;
		(*u).res=r-l+1;
		(*u).f=1;
		return ;
	}
	int m=(l+r)>>1;
	upd(getl(u),l,m,tl,tr);
	upd(getr(u),m+1,r,tl,tr);
	(*u).res=(*getr(u)).res+((*getl(u)).res);
}

int pors(node *u,int l,int r,int tl,int tr){
	if(l>r||l>tr||r<tl||tl>tr||(*u).res==0){
		return 0;
	}
	if(((*u).f)==1){
		return min(r,tr)-max(l,tl)+1;
	}
	int m=(l+r)>>1;
	return pors(getl(u),l,m,tl,tr)+pors(getr(u),m+1,r,tl,tr);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	for(int asd=0;asd<t;asd++){
		int qq;
		cin>>qq;
		int l,r;
		cin>>l>>r;
		l+=c;
		r+=c;
		if(qq==1){
			int res=pors(&rishe,0,1073741824-1,l,r);
			cout<<res<<"\n";
			c=res;
		}else{
			upd(&rishe,0,1073741824-1,l,r);
		}
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...