Submission #998413

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
998413	2024-06-14T00:13:08 Z	amirhoseinfar1385	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	58 ms	16576 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(1000000);
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	6 ms	15944 KB	Output is correct
2	Correct	5 ms	15964 KB	Output is correct
3	Correct	6 ms	15964 KB	Output is correct
4	Correct	8 ms	16020 KB	Output is correct
5	Correct	9 ms	15964 KB	Output is correct
6	Correct	9 ms	16144 KB	Output is correct
7	Correct	9 ms	15964 KB	Output is correct
8	Correct	19 ms	16284 KB	Output is correct
9	Correct	44 ms	16468 KB	Output is correct
10	Correct	32 ms	16476 KB	Output is correct
11	Correct	31 ms	16336 KB	Output is correct
12	Correct	32 ms	16472 KB	Output is correct
13	Correct	42 ms	16444 KB	Output is correct
14	Correct	58 ms	16468 KB	Output is correct
15	Correct	31 ms	16476 KB	Output is correct
16	Correct	30 ms	16476 KB	Output is correct
17	Correct	42 ms	16476 KB	Output is correct
18	Correct	45 ms	16576 KB	Output is correct
19	Correct	31 ms	16528 KB	Output is correct
20	Correct	31 ms	16480 KB	Output is correct