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

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.0 / 100.0

#	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