Submission #853261

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
853261	2023-09-23T19:05:46 Z	serifefedartar	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	360 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 main() {
	fast
	int M, D, X, Y;
	cin >> M;

	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	1 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	13 ms	8540 KB	Output is correct
5	Correct	17 ms	10336 KB	Output is correct
6	Correct	18 ms	9964 KB	Output is correct
7	Correct	21 ms	10328 KB	Output is correct
8	Correct	145 ms	77156 KB	Output is correct
9	Correct	274 ms	130900 KB	Output is correct
10	Correct	296 ms	146864 KB	Output is correct
11	Correct	325 ms	159276 KB	Output is correct
12	Correct	318 ms	164964 KB	Output is correct
13	Correct	300 ms	205008 KB	Output is correct
14	Correct	328 ms	207160 KB	Output is correct
15	Runtime error	360 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-