Submission #853256

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
853256	2023-09-23T18:49:05 Z	serifefedartar	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	359 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 query(node->ptrL, a, b) + 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	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	16 ms	8540 KB	Output is correct
5	Correct	16 ms	10300 KB	Output is correct
6	Correct	18 ms	9932 KB	Output is correct
7	Correct	17 ms	10332 KB	Output is correct
8	Correct	143 ms	77096 KB	Output is correct
9	Correct	290 ms	130916 KB	Output is correct
10	Correct	310 ms	147028 KB	Output is correct
11	Correct	313 ms	159448 KB	Output is correct
12	Correct	307 ms	164940 KB	Output is correct
13	Correct	302 ms	205340 KB	Output is correct
14	Correct	302 ms	206976 KB	Output is correct
15	Runtime error	359 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-