Submission #410566

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
410566	2021-05-23T02:32:02 Z	dreezy	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	2000 ms	151084 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 = 100006;
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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	90 ms	150492 KB	Output is correct
2	Correct	83 ms	150484 KB	Output is correct
3	Correct	85 ms	150572 KB	Output is correct
4	Correct	109 ms	150596 KB	Output is correct
5	Correct	117 ms	150544 KB	Output is correct
6	Correct	114 ms	150548 KB	Output is correct
7	Correct	116 ms	150536 KB	Output is correct
8	Correct	297 ms	150804 KB	Output is correct
9	Correct	520 ms	150940 KB	Output is correct
10	Correct	534 ms	150936 KB	Output is correct
11	Correct	539 ms	150872 KB	Output is correct
12	Correct	535 ms	150932 KB	Output is correct
13	Correct	503 ms	151020 KB	Output is correct
14	Correct	500 ms	151084 KB	Output is correct
15	Execution timed out	2080 ms	150980 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-