Submission #1112537

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1112537	2024-11-14T09:41:07 Z	Tsagana	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	1 ms	336 KB

apple

#include <bits/stdc++.h>
using namespace std;

#define int long long

struct segment_tree {
	struct node {
		int L, R;
		int sum;
		int lazy;
		node *left, *right;

		int mid() {
			return (L + R) / 2;
		}

		node(int x, int y) {
			L = x; R = y;
			sum = 0;
			lazy = 0;
			left = nullptr;
			right = nullptr;
		}

		int value() {
			return sum + lazy * (R - L + 1);
		}

		void extract() {
			if (L == R) return;
			if (left != nullptr) return;
			int M = mid();
			left = new node(L, M);
			right = new node(M + 1, R);
		}

		void update(int l, int r) {
			if (L == l && r == R) {
				collapse();
				sum = 0;
				lazy = 1;
				return;
			}
			if (lazy > 0) return;
			extract();
			int M = mid();
			if (r <= M) left -> update(l, r);
			else if (M < l) right -> update(l, r);
			else {
				left -> update(l, M);
				right -> update(M + 1, r);
			}
			sum = left -> value() + right -> value();
		}

		int query(int l, int r) {
			if (L == l && r == R) return value();
			if (left == nullptr) return lazy * (r - l + 1);
			int M = mid();
			if (r <= M) return left -> query(l, r) + lazy * (r - l + 1);
			else if (M < l) return right -> query(l, r) + lazy * (r - l + 1);
			
			return left -> query(l, M) +
				   right -> query(M + 1, r) +
			       lazy * (r - l + 1);
		
		}

		void collapse() {
			if (left != nullptr) {
				left -> collapse();
				delete left;
			}
			if (right != nullptr) {
				right -> collapse();
				delete right;
			}
		}
	} *root;

	segment_tree(int x, int y) {
		root = new node(x, y);
	}

	void update(int l, int r) {
		root -> update(l, r);
	}

	int query(int l, int r) {
		return root -> query(l, r);
	}
};

int32_t main() {
	int q; cin >> q;
	int c = 0;

	segment_tree st(1, 1e9);

	while (q--) {
		int d, l, r;
		cin >> d >> l >> r;
		if (l + c <= 0 || l + c > 1e9) return 0;
		if (r + c <= 0 || r + c > 1e9) return 0;
		if (d == 1) {
			c = st.query(l + c, r + c);
			cout << c << endl;
		} else {
			st.update(l + c, r + c);
			//cout << st.root->sum << endl;
		}
	}
	return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Runtime error	1 ms	336 KB	Execution killed with signal 6
4	Halted	0 ms	0 KB	-