Submission #853260

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
853260	2023-09-23T19:01:15 Z	serifefedartar	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	370 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->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 (node->ptrL == NULL ? 0 : query(node->ptrL, a, b)) + (node->ptrR == NULL ? 0 : 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

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	13 ms	8540 KB	Output is correct
5	Correct	17 ms	10332 KB	Output is correct
6	Correct	16 ms	10076 KB	Output is correct
7	Correct	16 ms	10328 KB	Output is correct
8	Correct	142 ms	77100 KB	Output is correct
9	Correct	299 ms	131120 KB	Output is correct
10	Correct	306 ms	146820 KB	Output is correct
11	Correct	329 ms	159420 KB	Output is correct
12	Correct	329 ms	165088 KB	Output is correct
13	Correct	323 ms	205020 KB	Output is correct
14	Correct	308 ms	207100 KB	Output is correct
15	Runtime error	370 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-