Submission #1112539

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1112539	2024-11-14T09:41:59 Z	Tsagana	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	147 ms	2972 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;
				left = nullptr;
			}
			if (right != nullptr) {
				right -> collapse();
				delete right;
				right = nullptr;
			}
		}
	} *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

100.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	Correct	1 ms	336 KB	Output is correct
4	Correct	13 ms	572 KB	Output is correct
5	Correct	18 ms	592 KB	Output is correct
6	Correct	14 ms	592 KB	Output is correct
7	Correct	19 ms	768 KB	Output is correct
8	Correct	66 ms	1352 KB	Output is correct
9	Correct	129 ms	2376 KB	Output is correct
10	Correct	128 ms	2376 KB	Output is correct
11	Correct	129 ms	2376 KB	Output is correct
12	Correct	139 ms	2552 KB	Output is correct
13	Correct	138 ms	2888 KB	Output is correct
14	Correct	139 ms	2796 KB	Output is correct
15	Correct	134 ms	2888 KB	Output is correct
16	Correct	142 ms	2888 KB	Output is correct
17	Correct	131 ms	2796 KB	Output is correct
18	Correct	129 ms	2972 KB	Output is correct
19	Correct	133 ms	2888 KB	Output is correct
20	Correct	147 ms	2968 KB	Output is correct