답안 #410564

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
410564	2021-05-23T02:28:56 Z	dreezy	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	407 ms	262148 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 = 1e5;
node segtree[17*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

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	40140 KB	Output is correct
2	Correct	23 ms	40188 KB	Output is correct
3	Correct	23 ms	40176 KB	Output is correct
4	Correct	49 ms	40216 KB	Output is correct
5	Correct	53 ms	40228 KB	Output is correct
6	Correct	55 ms	40140 KB	Output is correct
7	Correct	54 ms	40228 KB	Output is correct
8	Correct	235 ms	40268 KB	Output is correct
9	Runtime error	407 ms	262148 KB	Execution killed with signal 9
10	Halted	0 ms	0 KB	-