답안 #853326

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
853326	2023-09-24T06:47:50 Z	serifefedartar	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	1081 ms	262144 KB

apple

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 20;
const ll MAXN = 1e5 + 5;

struct Node {
	int l, r, sum;
	bool lazy;
	int left, right;
	Node(int a, int b) : l(a), r(b), sum(0), lazy(0), left(-1), right(-1) { }
	Node() : l(-1), r(-1), sum(0), lazy(0), left(-1), right(-1) { }
};
Node sg[60*MAXN];
int no = 2;

void add(int x) {
	if (sg[x].left == -1 && sg[x].l != sg[x].r) {
		int mid = (sg[x].l + sg[x].r) / 2;
		sg[x].left = no;
		sg[x].right = no+1;
		sg[no++] = Node(sg[x].l, mid);
		sg[no++] = Node(mid+1, sg[x].r);
	}
}

void push(int x) {
	if (sg[x].lazy) {
		sg[x].sum = sg[x].r - sg[x].l + 1;
		if (sg[x].l != sg[x].r) {
			add(x);
			sg[sg[x].left].lazy = 1;
			sg[sg[x].left].sum = sg[sg[x].left].r - sg[sg[x].left].l + 1;
			sg[sg[x].right].lazy = 1;
			sg[sg[x].right].sum = sg[sg[x].right].r - sg[sg[x].right].l + 1;
		}
		sg[x].lazy = 0;
	}
}

void update(int x, int a, int b) {
	if (sg[x].l > b || a > sg[x].r)
		return ;
	if (a <= sg[x].l && sg[x].r <= b) {
		sg[x].lazy = 1;
		push(x);
		return ;
	}
	add(x);
	push(x);
	update(sg[x].left, a, b);
	update(sg[x].right, a, b);
	sg[x].sum = sg[sg[x].left].sum + sg[sg[x].right].sum; 
}

int query(int x, int a, int b) {
	if (sg[x].l > b || a > sg[x].r)
		return 0;
	push(x);
	if (a <= sg[x].l && sg[x].r <= b)
		return sg[x].sum;
	add(x);
	return query(sg[x].left, a, b) + query(sg[x].right, a, b);
}

int M, D, X, Y, C = 0;
int main() {
	fast
	cin >> M;

	sg[1] = Node(1, 1e9); 
	while (M--) {
		cin >> D >> X >> Y;
		if (D == 1) {
			C = query(1, X + C, Y + C);
			cout << C << "\n";
		} else
			update(1, X + C, Y + C);
	}
}

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	141148 KB	Output is correct
2	Correct	25 ms	141148 KB	Output is correct
3	Correct	25 ms	141140 KB	Output is correct
4	Correct	33 ms	141404 KB	Output is correct
5	Correct	35 ms	141400 KB	Output is correct
6	Correct	34 ms	141404 KB	Output is correct
7	Correct	35 ms	141496 KB	Output is correct
8	Correct	96 ms	142164 KB	Output is correct
9	Correct	179 ms	143308 KB	Output is correct
10	Correct	195 ms	143412 KB	Output is correct
11	Correct	190 ms	143396 KB	Output is correct
12	Correct	187 ms	143516 KB	Output is correct
13	Correct	169 ms	143652 KB	Output is correct
14	Correct	167 ms	141760 KB	Output is correct
15	Runtime error	1081 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-