답안 #853256

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
853256	2023-09-23T18:49:05 Z	serifefedartar	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	359 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, 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->ptrR->lazy = 1;
		}
		node->lazy = 0;
	}
}

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

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

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

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	16 ms	8540 KB	Output is correct
5	Correct	16 ms	10300 KB	Output is correct
6	Correct	18 ms	9932 KB	Output is correct
7	Correct	17 ms	10332 KB	Output is correct
8	Correct	143 ms	77096 KB	Output is correct
9	Correct	290 ms	130916 KB	Output is correct
10	Correct	310 ms	147028 KB	Output is correct
11	Correct	313 ms	159448 KB	Output is correct
12	Correct	307 ms	164940 KB	Output is correct
13	Correct	302 ms	205340 KB	Output is correct
14	Correct	302 ms	206976 KB	Output is correct
15	Runtime error	359 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-