Submission #853259

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
853259	2023-09-23T18:57:43 Z	serifefedartar	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	341 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 (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	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	14 ms	8536 KB	Output is correct
5	Correct	16 ms	10328 KB	Output is correct
6	Correct	16 ms	10072 KB	Output is correct
7	Correct	16 ms	10328 KB	Output is correct
8	Correct	135 ms	77140 KB	Output is correct
9	Correct	292 ms	130900 KB	Output is correct
10	Correct	295 ms	146852 KB	Output is correct
11	Correct	314 ms	159704 KB	Output is correct
12	Correct	314 ms	164944 KB	Output is correct
13	Correct	306 ms	205016 KB	Output is correct
14	Correct	290 ms	207104 KB	Output is correct
15	Runtime error	341 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-