Submission #410568

#	Time	Username	Problem	Language	Result	Execution time	Memory
410568		dreezy	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	652 ms	186340 KiB

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 / 100