제출 #1112534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1112534		Tsagana	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	2 ms	592 KiB

apple

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

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);
	}
};

int 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