답안 #957949

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
957949 2024-04-04T14:04:28 Z bmh123456789asdf 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
319 ms 188500 KB
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#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 pushlazy(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) {
	pushlazy(node);
	if (l == segtree[node].tl && r == segtree[node].tr) {
		segtree[node].lazy = 1;
		pushlazy(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);
		}

		pushlazy(segtree[node].l);
		pushlazy(segtree[node].r);
		segtree[node].sum =
		    segtree[segtree[node].l].sum + segtree[segtree[node].r].sum;
	}
}


int query(int node,int l,int r)
{
	pushlazy(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 70 ms 185940 KB Output is correct
2 Correct 56 ms 185980 KB Output is correct
3 Correct 55 ms 185964 KB Output is correct
4 Correct 63 ms 186036 KB Output is correct
5 Correct 69 ms 185960 KB Output is correct
6 Correct 69 ms 185940 KB Output is correct
7 Correct 66 ms 186008 KB Output is correct
8 Correct 147 ms 186892 KB Output is correct
9 Correct 242 ms 188156 KB Output is correct
10 Correct 241 ms 187828 KB Output is correct
11 Correct 239 ms 187888 KB Output is correct
12 Correct 268 ms 187796 KB Output is correct
13 Correct 218 ms 188320 KB Output is correct
14 Correct 230 ms 188500 KB Output is correct
15 Correct 300 ms 188320 KB Output is correct
16 Correct 319 ms 188484 KB Output is correct
17 Correct 244 ms 188460 KB Output is correct
18 Correct 205 ms 188444 KB Output is correct
19 Correct 281 ms 188316 KB Output is correct
20 Correct 280 ms 188488 KB Output is correct