Submission #985525

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
985525	2024-05-18T04:45:53 Z	Troll321	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	475 ms	262144 KB

apple

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll MAX = 1e9;

struct node {
	node *left, *right;
	ll val, lazy;
	node() {
		val = 0;
		lazy = 0;
		left = nullptr;
		right = nullptr; 
	}
};

void updateLazy(node* now, ll l, ll r) {
	if(now->lazy == 1) {
		now->val = r-l+1;
		if(l != r) {
			if(!(now->left)) {now->left = new node();}
			if(!(now->right)) {now->right = new node();}
			now->left->lazy = 1;
			now->right->lazy = 1;
		}
		now->lazy = 0;
	}
}

void update(node* now, ll l, ll r, ll a, ll b) {
	// Update Lazy
	updateLazy(now, l, r);

	if (l > b || r < a) {
		return ;
	}
	if(a <= l && r <= b) {
		now->val = (r-l+1);
		// Propagate Lazy
		if(l != r) {
			if(!(now->left)) {now->left = new node();}
			if(!(now->right)) {now->right = new node();}
			now->left->lazy = 1;
			now->right->lazy = 1;
		}
		return ;
	}

	if (!(now->left)) {
		now->left = new node();
	}
	if(!(now->right)) {
		now->right = new node();
	}

	ll mid = (l+r)/2;
	update(now->left, l, mid, a, b);
	update(now->right, mid+1, r, a, b);
	now->val = now->left->val + now->right->val;
	return ;
}

ll query(node* now, ll l, ll r, ll a, ll b) {
	// Update Lazy
	updateLazy(now, l, r);

	if (!now || l > b || r < a) {
		return 0;
	}
	if(a <= l && r <= b) {
		return now->val;
	}
	ll mid = (l+r)/2;
	ll out = 0;
	if (now->left) {
		out += query(now->left, l, mid, a, b);
	}
	if(now->right) {
		out += query(now->right, mid+1, r, a, b);
	}
	return out;
}

ll q, c = 0;
node root;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> q;
	while(q--) {
		ll type, ql, qr;
		cin >> type >> ql >> qr;
		if (type == 1) {
			c = query(&root, 1, MAX, ql+c, qr+c);
			cout << c << "\n";
		} else {
			update(&root, 1, MAX, ql+c, qr+c);
		}
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	11 ms	5980 KB	Output is correct
5	Correct	20 ms	7004 KB	Output is correct
6	Correct	14 ms	6792 KB	Output is correct
7	Correct	14 ms	7164 KB	Output is correct
8	Correct	112 ms	51492 KB	Output is correct
9	Correct	236 ms	87344 KB	Output is correct
10	Correct	255 ms	98128 KB	Output is correct
11	Correct	262 ms	106412 KB	Output is correct
12	Correct	271 ms	110192 KB	Output is correct
13	Correct	253 ms	137040 KB	Output is correct
14	Correct	246 ms	138324 KB	Output is correct
15	Correct	475 ms	254588 KB	Output is correct
16	Correct	429 ms	256488 KB	Output is correct
17	Correct	258 ms	145336 KB	Output is correct
18	Correct	251 ms	145488 KB	Output is correct
19	Correct	439 ms	262144 KB	Output is correct
20	Correct	469 ms	262144 KB	Output is correct