Submission #911346

# Submission time Handle Problem Language Result Execution time Memory
911346 2024-01-18T19:10:25 Z happypotato Monkey and Apple-trees (IZhO12_apple) C++17
100 / 100
424 ms 207796 KB
#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();
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 14 ms 5036 KB Output is correct
5 Correct 20 ms 5972 KB Output is correct
6 Correct 20 ms 5968 KB Output is correct
7 Correct 18 ms 5980 KB Output is correct
8 Correct 129 ms 44716 KB Output is correct
9 Correct 275 ms 77216 KB Output is correct
10 Correct 308 ms 85328 KB Output is correct
11 Correct 290 ms 91472 KB Output is correct
12 Correct 303 ms 94460 KB Output is correct
13 Correct 276 ms 109900 KB Output is correct
14 Correct 270 ms 111152 KB Output is correct
15 Correct 415 ms 201812 KB Output is correct
16 Correct 424 ms 203200 KB Output is correct
17 Correct 268 ms 114764 KB Output is correct
18 Correct 269 ms 114964 KB Output is correct
19 Correct 416 ms 207656 KB Output is correct
20 Correct 419 ms 207796 KB Output is correct