답안 #344432

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
344432 2021-01-05T19:24:54 Z Tosic 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
249 ms 75756 KB
#include <bits/stdc++.h>
#define maxn 5000010
using namespace std;

int n, ans;
int tree[maxn], lChild[maxn], rChild[maxn], lazy[maxn], treeSize;

void makeL(int idx){
	if(!lChild[idx]){
			lChild[idx] = treeSize;
			++treeSize;
		}
}
void makeR(int idx){
	if(!rChild[idx]){
			rChild[idx] = treeSize;
			++treeSize;
		}
}

void prop(int idx, int l, int r){
	if(lazy[idx]){
		tree[idx] = r-l+1;
		lazy[idx] = 0;
		makeR(idx);
		makeL(idx);
		lazy[lChild[idx]] = 1;
		lazy[rChild[idx]] = 1;
	}

}

void upd(int idx, int l, int r, int ql, int qr){
	prop(idx, l, r);
	if(l >= ql and r<=qr){
		lazy[idx] = 1;
		prop(idx, l, r);
		return;
	}
	if(l > qr or r< ql){
		return;
	}
	makeL(idx);
	makeR(idx);
	int mid = (l+r)/2;
	upd(lChild[idx], l, mid, ql, qr);
	upd(rChild[idx], mid+1, r, ql, qr);
	tree[idx] = tree[rChild[idx]]+tree[lChild[idx]];
}

int cnt(int idx, int l, int r, int ql, int qr){
	prop(idx, l, r);
	if(l >= ql and r<= qr){
		return tree[idx];
	}
	if(r < ql or l > qr){
		return 0;
	}
	if(tree[idx] == (r-l+1)){
		return min(min(qr-l+1, r-ql+1), qr-ql+1);
	}
	if(!tree[idx]){
		return 0;
	}
	int mid=(l+r)/2, res = 0;
	if(rChild[idx]){
		res += cnt(rChild[idx], mid+1, r, ql, qr);
	}
	if(lChild[idx]){
		res += cnt(lChild[idx], l, mid, ql, qr);
	}
	return res;
}

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin >> n;
	treeSize=1;
	for(int i = 0; i < n; ++i){
		int k,x,y;
		cin>>k;
		if(k == 1){
			cin>>x >>y;
			ans=cnt(0, 0, 1e9+1, x+ans, y+ans);
			cout << ans << '\n';
		} else {
			cin>> x>>y;
			upd(0, 0, 1e9+1, x+ans, y+ans);
		}
	}
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 11 ms 2156 KB Output is correct
5 Correct 12 ms 2540 KB Output is correct
6 Correct 12 ms 2540 KB Output is correct
7 Correct 13 ms 2540 KB Output is correct
8 Correct 88 ms 17900 KB Output is correct
9 Correct 182 ms 31724 KB Output is correct
10 Correct 190 ms 34540 KB Output is correct
11 Correct 191 ms 36716 KB Output is correct
12 Correct 191 ms 37612 KB Output is correct
13 Correct 175 ms 39532 KB Output is correct
14 Correct 184 ms 40300 KB Output is correct
15 Correct 242 ms 74092 KB Output is correct
16 Correct 249 ms 74252 KB Output is correct
17 Correct 185 ms 42016 KB Output is correct
18 Correct 175 ms 42080 KB Output is correct
19 Correct 246 ms 75732 KB Output is correct
20 Correct 243 ms 75756 KB Output is correct