Submission #998411

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
998411	2024-06-14T00:12:27 Z	amirhoseinfar1385	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	55 ms	49160 KB

apple

#include<bits/stdc++.h>
using namespace std;
int c;
struct node{
	int cl,cr;
	int res=0,f=0;
	node(){
		cl=cr=-1;
		res=f=0;
	}
}fakenode;
vector<node>all(3000000);
int te=1;

int getl(int u){
	if(all[u].cl==-1){
		all[u].cl=te;
		te++;
	}
	return all[u].cl;
}

int getr(int u){
	if(all[u].cr==-1){
		all[u].cr=te;
		te++;
	}
	return all[u].cr;
}

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

int pors(int u,int l,int r,int tl,int tr){
	if(l>r||l>tr||r<tl||tl>tr||all[u].res==0){
		return 0;
	}
	if((all[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(0,0,1073741824-1,l,r);
			cout<<res<<"\n";
			c=res;
		}else{
			upd(0,0,1073741824-1,l,r);
		}
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	47192 KB	Output is correct
2	Correct	17 ms	47196 KB	Output is correct
3	Correct	16 ms	47196 KB	Output is correct
4	Correct	20 ms	47448 KB	Output is correct
5	Correct	20 ms	47452 KB	Output is correct
6	Correct	20 ms	47452 KB	Output is correct
7	Correct	19 ms	47424 KB	Output is correct
8	Correct	29 ms	48212 KB	Output is correct
9	Correct	43 ms	48724 KB	Output is correct
10	Correct	49 ms	48724 KB	Output is correct
11	Correct	47 ms	48772 KB	Output is correct
12	Correct	46 ms	48804 KB	Output is correct
13	Correct	53 ms	48980 KB	Output is correct
14	Correct	54 ms	49160 KB	Output is correct
15	Correct	51 ms	48976 KB	Output is correct
16	Correct	48 ms	48980 KB	Output is correct
17	Correct	55 ms	48980 KB	Output is correct
18	Correct	55 ms	48976 KB	Output is correct
19	Correct	43 ms	48988 KB	Output is correct
20	Correct	43 ms	48980 KB	Output is correct