Submission #985524

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

apple

#include <bits/stdc++.h>
using namespace std;
typedef long long 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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	13 ms	8840 KB	Output is correct
5	Correct	15 ms	10588 KB	Output is correct
6	Correct	16 ms	10076 KB	Output is correct
7	Correct	17 ms	10588 KB	Output is correct
8	Correct	137 ms	78000 KB	Output is correct
9	Correct	267 ms	132688 KB	Output is correct
10	Correct	312 ms	148544 KB	Output is correct
11	Correct	299 ms	161204 KB	Output is correct
12	Correct	312 ms	166688 KB	Output is correct
13	Correct	272 ms	207188 KB	Output is correct
14	Correct	297 ms	209524 KB	Output is correct
15	Runtime error	349 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-