Submission #853262

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
853262	2023-09-23T19:07:38 Z	serifefedartar	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	366 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));
}

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	8540 KB	Output is correct
5	Correct	20 ms	10440 KB	Output is correct
6	Correct	16 ms	10076 KB	Output is correct
7	Correct	16 ms	10328 KB	Output is correct
8	Correct	139 ms	77020 KB	Output is correct
9	Correct	284 ms	130908 KB	Output is correct
10	Correct	298 ms	146812 KB	Output is correct
11	Correct	336 ms	159324 KB	Output is correct
12	Correct	338 ms	164792 KB	Output is correct
13	Correct	299 ms	205140 KB	Output is correct
14	Correct	333 ms	207344 KB	Output is correct
15	Runtime error	366 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-