Submission #853266

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
853266	2023-09-23T19:17:11 Z	serifefedartar	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	399 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) {
	if (node->l > b || a > node->r)
		return 0;
	push(node);
	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	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	12 ms	6748 KB	Output is correct
5	Correct	15 ms	8280 KB	Output is correct
6	Correct	15 ms	7896 KB	Output is correct
7	Correct	14 ms	8280 KB	Output is correct
8	Correct	124 ms	61260 KB	Output is correct
9	Correct	263 ms	104788 KB	Output is correct
10	Correct	280 ms	116816 KB	Output is correct
11	Correct	277 ms	126028 KB	Output is correct
12	Correct	286 ms	130208 KB	Output is correct
13	Correct	250 ms	157416 KB	Output is correct
14	Correct	253 ms	158788 KB	Output is correct
15	Runtime error	399 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-