답안 #736808

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
736808 2023-05-06T08:50:31 Z MODDI 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
406 ms 188596 KB
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
struct Node{
	int sum, lazy, tl, tr, l, r;
	Node() : sum(0), lazy(0), l(-1), r(-1){}
};
Node tree[64 * 123456];
int cnt = 2;
void push_lazy(int node){
	if(tree[node].lazy){
		tree[node].sum= tree[node].tr - tree[node].tl + 1;
		int mid = (tree[node].tl + tree[node].tr) / 2;
		if(tree[node].l == -1){
			tree[node].l = cnt++;
			tree[tree[node].l].tl = tree[node].tl;
			tree[tree[node].l].tr = mid;
		}
		if(tree[node].r == -1){
			tree[node].r = cnt++;
			tree[tree[node].r].tl = mid+1;
			tree[tree[node].r].tr = tree[node].tr;
		}
		tree[tree[node].l].lazy = tree[tree[node].r].lazy = 1;
		tree[node].lazy = 0;
	}
}
void update(int node, int l, int r){
	push_lazy(node);
	if(l == tree[node].tl && tree[node].tr == r){
		tree[node].lazy = 1;
		push_lazy(node);
	}
	else{
		int mid = (tree[node].tl + tree[node].tr) / 2;
		if(tree[node].l == -1){
			tree[node].l = cnt++;
			tree[tree[node].l].tl = tree[node].tl;
			tree[tree[node].l].tr = mid;
		}
		if(tree[node].r == -1){
			tree[node].r = cnt++;
			tree[tree[node].r].tl = mid+1;
			tree[tree[node].r].tr = tree[node].tr;
		}
		if(l > mid)	update(tree[node].r, l, r);
		else if(r <= mid)	update(tree[node].l, l, r);
		else{
			update(tree[node].l, l, mid);
			update(tree[node].r, mid+1, r);
		}
		push_lazy(tree[node].l);
		push_lazy(tree[node].r);
		tree[node].sum = tree[tree[node].l].sum + tree[tree[node].r].sum;
	}
}
int query(int node, int l, int r){
	push_lazy(node);
	if(l == tree[node].tl && r == tree[node].tr){
		return tree[node].sum;	
	}
	else{
		int mid = (tree[node].tl + tree[node].tr )/2;
		if(tree[node].l == -1){
			tree[node].l = cnt++;
			tree[tree[node].l].tl = tree[node].tl;
			tree[tree[node].l].tr = mid;
		}
		if(tree[node].r == -1){
			tree[node].r = cnt++;
			tree[tree[node].r].tl = mid+1;
			tree[tree[node].r].tr = tree[node].tr;
		}
		if(l > mid)	return query(tree[node].r, l, r);
		else if(r <= mid)	return query(tree[node].l, l, r);
		else{
			return query(tree[node].l, l, mid) + query(tree[node].r, mid+1, r);
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	tree[1].sum = 0;
	tree[1].lazy = 0;
	tree[1].tl = 1;
	tree[1].tr = 1e9;
	int c = 0;
	while(n--){
		int d, x, y;
		cin>>d>>x>>y;
		if(d == 1){
			c = query(1, x+c, y+c);
			cout<<c<<"\n";
		}
		else
			update(1, x+c, y+c);
	}

	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 185804 KB Output is correct
2 Correct 79 ms 185800 KB Output is correct
3 Correct 79 ms 185768 KB Output is correct
4 Correct 95 ms 185932 KB Output is correct
5 Correct 93 ms 186020 KB Output is correct
6 Correct 93 ms 186004 KB Output is correct
7 Correct 96 ms 186008 KB Output is correct
8 Correct 202 ms 186892 KB Output is correct
9 Correct 309 ms 187968 KB Output is correct
10 Correct 333 ms 187956 KB Output is correct
11 Correct 334 ms 187900 KB Output is correct
12 Correct 334 ms 187952 KB Output is correct
13 Correct 298 ms 188380 KB Output is correct
14 Correct 305 ms 188320 KB Output is correct
15 Correct 398 ms 188488 KB Output is correct
16 Correct 387 ms 188596 KB Output is correct
17 Correct 312 ms 188436 KB Output is correct
18 Correct 289 ms 188420 KB Output is correct
19 Correct 406 ms 188544 KB Output is correct
20 Correct 398 ms 188424 KB Output is correct