답안 #853265

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
853265	2023-09-23T19:15:50 Z	serifefedartar	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	394 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 = 2e5 + 5;

struct Node {
	int l, r, sum;
	bool lazy;
	Node *ptrL, *ptrR;
	Node(int a, int b) : l(a), r(b), sum(0), lazy(0), ptrL(NULL), ptrR(NULL) { };
};

void add(Node *node) {
	if (node->ptrL == NULL && node->l != node->r) {
		int mid = (node->l + node->r) / 2;
		node->ptrL = new Node(node->l, mid);
		node->ptrR = new Node(mid+1, node->r);
	}
}

void push(Node *node) {
	if (node->lazy) {
		node->sum = node->r - node->l + 1;
		if (node->l != node->r) {
			add(node);
			node->ptrL->lazy = 1;
			node->ptrL->sum = node->ptrL->r - node->ptrL->l + 1;
			node->ptrR->lazy = 1;
			node->ptrR->sum = node->ptrR->r - node->ptrR->l + 1;
		}
		node->lazy = 0;
	}
}

void update(Node *node, int a, int b) {
	if (node->l > b || a > node->r)
		return ;
	if (a <= node->l && node->r <= b) {
		node->lazy = 1;
		push(node);
		return ;
	}
	add(node);
	push(node);
	update(node->ptrL, a, b);
	update(node->ptrR, a, b);
	node->sum = node->ptrL->sum + node->ptrR->sum; 
}

int query(Node *node, int a, int b) {
	push(node);
	if (node->l > b || a > node->r)
		return 0;
	if (a <= node->l && node->r <= b)
		return node->sum;
	add(node);
	return (node->ptrL == NULL ? 0 : query(node->ptrL, a, b)) + (node->ptrR == NULL ? 0 : query(node->ptrR, a, b));
}

Node *root = new Node(1, 1e9);
int M, D, X, Y, C = 0;
int main() {
	fast
	cin >> M;

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

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	13 ms	7768 KB	Output is correct
5	Correct	16 ms	9308 KB	Output is correct
6	Correct	16 ms	9052 KB	Output is correct
7	Correct	16 ms	9380 KB	Output is correct
8	Correct	146 ms	69584 KB	Output is correct
9	Correct	296 ms	118352 KB	Output is correct
10	Correct	295 ms	132420 KB	Output is correct
11	Correct	320 ms	143444 KB	Output is correct
12	Correct	313 ms	148244 KB	Output is correct
13	Correct	285 ms	181976 KB	Output is correct
14	Correct	289 ms	183192 KB	Output is correct
15	Runtime error	394 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-