답안 #950306

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
950306 2024-03-20T07:53:37 Z nguyennh 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
292 ms 188556 KB
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define MOD 1000000007
typedef long long ll;
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 node) {
	if (segtree[node].lazy) {
		segtree[node].sum = segtree[node].tr - segtree[node].tl + 1;
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if (segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}
		segtree[segtree[node].l].lazy = segtree[segtree[node].r].lazy = 1;
		segtree[node].lazy = 0;
	}
}
 
void update(int node, int l, int r) {
	push_lazy(node);
	if (l == segtree[node].tl && r == segtree[node].tr) {
		segtree[node].lazy = 1;
		push_lazy(node);
	} else {
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if (segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}
 
		if (l > mid) update(segtree[node].r, l, r);
		else if (r <= mid) update(segtree[node].l, l, r);
		else {
			update(segtree[node].l, l, mid);
			update(segtree[node].r, mid + 1, r);
		}
 
		push_lazy(segtree[node].l);
		push_lazy(segtree[node].r);
		segtree[node].sum =
		    segtree[segtree[node].l].sum + segtree[segtree[node].r].sum;
	}
}
 
int query(int node, int l, int r) {
	push_lazy(node);
	if (l == segtree[node].tl && r == segtree[node].tr)
		return segtree[node].sum;
	else {
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if (segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}
 
		if (l > mid) return query(segtree[node].r, l, r);
		else if (r <= mid) return query(segtree[node].l, l, r);
		else
			return query(segtree[node].l, l, mid) +
			       query(segtree[node].r, mid + 1, r);
	}
}
 
int main() {
	iostream::sync_with_stdio(false);
	cin.tie(0);
	int m;
	cin >> m;
 
	segtree[1].sum = 0;
	segtree[1].lazy = 0;
	segtree[1].tl = 1;
	segtree[1].tr = 1e9;
 
	int c = 0;
	FOR(_, 0, m) {
		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 185872 KB Output is correct
2 Correct 48 ms 185844 KB Output is correct
3 Correct 45 ms 185944 KB Output is correct
4 Correct 52 ms 185940 KB Output is correct
5 Correct 56 ms 186196 KB Output is correct
6 Correct 53 ms 185948 KB Output is correct
7 Correct 52 ms 186096 KB Output is correct
8 Correct 116 ms 186820 KB Output is correct
9 Correct 220 ms 188152 KB Output is correct
10 Correct 207 ms 188108 KB Output is correct
11 Correct 234 ms 188064 KB Output is correct
12 Correct 226 ms 188088 KB Output is correct
13 Correct 192 ms 188404 KB Output is correct
14 Correct 186 ms 188348 KB Output is correct
15 Correct 266 ms 188556 KB Output is correct
16 Correct 274 ms 188496 KB Output is correct
17 Correct 199 ms 188496 KB Output is correct
18 Correct 188 ms 188536 KB Output is correct
19 Correct 265 ms 188416 KB Output is correct
20 Correct 292 ms 188484 KB Output is correct