Submission #410563

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
410563	2021-05-23T02:27:28 Z	dreezy	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	659 ms	188596 KB

apple

#include <bits/stdc++.h>
using namespace std;


struct node {
	int sum, lazy, tl, tr, l, r;
	node() : sum(0), lazy(0), l(-1), r(-1) {}
};


const int MAXN = 123456;
node segtree[64*MAXN];
int cnt = 2;


void push_lazy(int n){
	if(segtree[n].lazy){
		segtree[n].sum = segtree[n].tr - segtree[n].tl + 1;
		int mid = (segtree[n].tr + segtree[n].tl) /2;
		
		if(segtree[n].l == -1){
			segtree[n].l = cnt++;
			segtree[segtree[n].l].tl = segtree[n].tl;
			segtree[segtree[n].l].tr = mid;
		}
		if(segtree[n].r == -1){
			segtree[n].r = cnt++;
			segtree[segtree[n].r].tl = mid +1;
			segtree[segtree[n].r].tr = segtree[n].tr;
		}
		
	//cout <<n<<": " <<segtree[n].l <<", "<<segtree[n].r<<":"<<segtree[segtree[n].l].l <<", "<<segtree[segtree[n].r].l<<endl;
		segtree[segtree[n].l].lazy = segtree[segtree[n].r].lazy  = 1;
		segtree[n].lazy = 0;
	}
}


void update(int n, int l, int r){
	//cout << n << ": "<<l<<", "<<r<<"\t"<<segtree[n].l<<", "<<segtree[n].r<<"\t"<<segtree[n].tl<<", "<<segtree[n].tr<<endl;
	//cout << cnt<<endl;
	//if(cnt > 10) 	return;
	push_lazy(n);
	if(segtree[n].tl == l && segtree[n].tr == r){
		segtree[n].lazy = 1;
		push_lazy(n);
	}
	
	else{
		int mid = (segtree[n].tl + segtree[n].tr )/2;
		if(segtree[n].l == -1){
			segtree[n].l = cnt++;
			segtree[segtree[n].l].tl = segtree[n].tl;
			segtree[segtree[n].l].tr = mid;
		}
		if(segtree[n].r == -1){
			segtree[n].r = cnt++;
			segtree[segtree[n].r].tl = mid+1;
			segtree[segtree[n].r].tr = segtree[n].tr;
		}
		
		if( l <= mid){
			//cout << n<<"->"<<segtree[n].l<<endl;
			update(segtree[n].l, l, min(mid, r));
		}
		
		if( r > mid){
			update(segtree[n].r, max(l, mid+1), r);
		}
		
		push_lazy(segtree[n].l);
		push_lazy(segtree[n].r);
		segtree[n].sum = segtree[segtree[n].l].sum + segtree[segtree[n].r].sum;
	}
}

int query(int n, int l, int r){
	//cout << n << ": "<<l<<", "<<r<<"\t"<<segtree[n].l<<", "<<segtree[n].r<<endl;
	push_lazy(n);
	if(segtree[n].tl == l && segtree[n].tr == r){
		return segtree[n].sum;
	}
	
	else{
		int mid = (segtree[n].tl + segtree[n].tr )/2;
		if(segtree[n].l == -1){
			segtree[n].l = cnt++;
			segtree[segtree[n].l].tl = segtree[n].tl;
			segtree[segtree[n].l].tr = mid;
		}
		if(segtree[n].r == -1){
			segtree[n].r = cnt++;
			segtree[segtree[n].r].tl = mid+1;
			segtree[segtree[n].r].tr = segtree[n].tr;
		}
		int ans = 0;
		if( l <= mid){
			ans+=query(segtree[n].l, l, min(mid, r));
		}
		
		if( r > mid){
			ans+=query(segtree[n].r, max(l, mid+1), r);
		}
		
		return ans;
	}
	
}

int main(){
	int m; cin >> m;
	
	segtree[1].sum = 0;
	segtree[1].lazy = 0;
	segtree[1].tl =1;
	segtree[1].tr = 1e9;
	
	int c = 0;
	while(m--){
		int d,x,y; cin >> d >> x >> y;
		
		if(d == 2){
			update(1, x +c, y +c);
		}else{
			c = query(1, x +c, y+c);
			cout << c <<endl;
		}
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	104 ms	185728 KB	Output is correct
2	Correct	115 ms	185740 KB	Output is correct
3	Correct	104 ms	185796 KB	Output is correct
4	Correct	129 ms	185780 KB	Output is correct
5	Correct	133 ms	185804 KB	Output is correct
6	Correct	134 ms	185812 KB	Output is correct
7	Correct	136 ms	185828 KB	Output is correct
8	Correct	312 ms	186832 KB	Output is correct
9	Correct	556 ms	187968 KB	Output is correct
10	Correct	536 ms	187972 KB	Output is correct
11	Correct	579 ms	188100 KB	Output is correct
12	Correct	568 ms	187964 KB	Output is correct
13	Correct	522 ms	188356 KB	Output is correct
14	Correct	524 ms	188372 KB	Output is correct
15	Correct	638 ms	188424 KB	Output is correct
16	Correct	642 ms	188552 KB	Output is correct
17	Correct	522 ms	188356 KB	Output is correct
18	Correct	525 ms	188284 KB	Output is correct
19	Correct	652 ms	188596 KB	Output is correct
20	Correct	659 ms	188380 KB	Output is correct