Submission #410568

# Submission time Handle Problem Language Result Execution time Memory
410568 2021-05-23T02:33:06 Z dreezy Monkey and Apple-trees (IZhO12_apple) C++17
100 / 100
652 ms 186340 KB
#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;
		}
	}
}
# Verdict Execution time Memory Grader output
1 Correct 101 ms 185796 KB Output is correct
2 Correct 107 ms 185788 KB Output is correct
3 Correct 102 ms 185720 KB Output is correct
4 Correct 129 ms 185824 KB Output is correct
5 Correct 136 ms 185792 KB Output is correct
6 Correct 133 ms 185828 KB Output is correct
7 Correct 139 ms 185796 KB Output is correct
8 Correct 309 ms 185968 KB Output is correct
9 Correct 539 ms 186228 KB Output is correct
10 Correct 532 ms 186196 KB Output is correct
11 Correct 541 ms 186140 KB Output is correct
12 Correct 546 ms 186180 KB Output is correct
13 Correct 506 ms 186308 KB Output is correct
14 Correct 512 ms 186288 KB Output is correct
15 Correct 636 ms 186296 KB Output is correct
16 Correct 631 ms 186340 KB Output is correct
17 Correct 513 ms 186296 KB Output is correct
18 Correct 519 ms 186316 KB Output is correct
19 Correct 638 ms 186308 KB Output is correct
20 Correct 652 ms 186284 KB Output is correct