Submission #998412

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
998412	2024-06-14T00:12:51 Z	amirhoseinfar1385	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	48 ms	32092 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(2000000);
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	12 ms	31576 KB	Output is correct
2	Correct	15 ms	31532 KB	Output is correct
3	Correct	11 ms	31580 KB	Output is correct
4	Correct	13 ms	31580 KB	Output is correct
5	Correct	14 ms	31580 KB	Output is correct
6	Correct	20 ms	31616 KB	Output is correct
7	Correct	14 ms	31576 KB	Output is correct
8	Correct	24 ms	31920 KB	Output is correct
9	Correct	38 ms	32080 KB	Output is correct
10	Correct	37 ms	32036 KB	Output is correct
11	Correct	36 ms	32076 KB	Output is correct
12	Correct	36 ms	32088 KB	Output is correct
13	Correct	47 ms	32080 KB	Output is correct
14	Correct	47 ms	32080 KB	Output is correct
15	Correct	36 ms	32024 KB	Output is correct
16	Correct	45 ms	32092 KB	Output is correct
17	Correct	48 ms	32084 KB	Output is correct
18	Correct	47 ms	32056 KB	Output is correct
19	Correct	47 ms	32080 KB	Output is correct
20	Correct	36 ms	32092 KB	Output is correct