Submission #985525

#	Time	Username	Problem	Language	Result	Execution time	Memory
985525		Troll321	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	475 ms	262144 KiB

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 / 100