Submission #998404

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
998404	2024-06-14T00:05:46 Z	amirhoseinfar1385	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	60 ms	3112 KB

apple

#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);
		}
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	3 ms	580 KB	Output is correct
5	Correct	4 ms	468 KB	Output is correct
6	Correct	4 ms	600 KB	Output is correct
7	Correct	4 ms	600 KB	Output is correct
8	Correct	16 ms	1368 KB	Output is correct
9	Correct	37 ms	2564 KB	Output is correct
10	Correct	26 ms	2384 KB	Output is correct
11	Correct	26 ms	2396 KB	Output is correct
12	Correct	26 ms	2396 KB	Output is correct
13	Correct	60 ms	2896 KB	Output is correct
14	Correct	37 ms	2868 KB	Output is correct
15	Correct	25 ms	3032 KB	Output is correct
16	Correct	42 ms	3112 KB	Output is correct
17	Correct	37 ms	2908 KB	Output is correct
18	Correct	36 ms	2896 KB	Output is correct
19	Correct	26 ms	2908 KB	Output is correct
20	Correct	25 ms	2908 KB	Output is correct