Submission #911346

#	Time	Username	Problem	Language	Result	Execution time	Memory
911346		happypotato	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	424 ms	207796 KiB

apple

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
struct node {
	int ans, l, r;
	bool all;
	node *left, *right;
	node(int l_, int r_): ans(0), l(l_), r(r_), all(false), left(nullptr), right(nullptr) {};
};
const int MAX = 1e9;
node *seg = new node(1, MAX);
void pushdown(node *cur) {
	int mid = (cur->l + cur->r) >> 1;
	if (cur->left == nullptr) cur->left = new node(cur->l, mid);
	if (cur->right == nullptr) cur->right = new node(mid + 1, cur->r);
	if (cur->all) {
		cur->left->ans = mid - cur->l + 1;
		cur->left->all = true;
		cur->right->ans = cur->r - mid;
		cur->right->all = true;
	}
}
void update(int tl, int tr, node *cur = seg) {
	if (tl <= cur->l && cur->r <= tr) {
		cur->ans = (cur->r - cur->l + 1);
		cur->all = true;
		return;
	}
	pushdown(cur);
	int mid = (cur->l + cur->r) >> 1;
	if (tl <= mid) update(tl, tr, cur->left);
	if (tr > mid) update(tl, tr, cur->right);
	cur->ans = cur->left->ans + cur->right->ans;
}
int query(int tl, int tr, node *cur = seg) {
	if (tl <= cur->l && cur->r <= tr) {
		return cur->ans;
	}
	pushdown(cur);
	int mid = (cur->l + cur->r) >> 1;
	int res = 0;
	if (tl <= mid) res += query(tl, tr, cur->left);
	if (tr > mid) res += query(tl, tr, cur->right);
	return res;
}
void solve() {
	int q;
	cin >> q;
	int C = 0;
	while (q--) {
		int cmd, l, r;
		cin >> cmd >> l >> r;
		if (cmd == 1) {
			C = query(l + C, r + C);
			cout << C << endl;
		} else if (cmd == 2) {
			update(l + C, r + C);
		}
	}
}
int32_t main() {
	ios::sync_with_stdio(false); cin.tie(0);
	solve();
}

• Subtask 1: 100 / 100