Submission #1129406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129406		xnqs	Growing Trees (BOI11_grow)	C++20	100 / 100	276 ms	5328 KiB

grow

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <random>

std::mt19937 rng(53);

namespace Treap {
struct Node {
	int val;
	int size;
	int lazy;
	int prio;
	Node* l;
	Node* r;
	Node(int val = 0):
		val(val), size(1), lazy(0), prio(rng()), l(nullptr), r(nullptr) {}
};

Node* _aux_split_l = nullptr;
Node* _aux_split_r = nullptr;
Node* _aux_merge = nullptr;

inline int GetNodeSize(Node* node) {
	if (!node) {
		return 0;
	}
	return node->size;
}

inline void UpdateNodeSize(Node* node) {
	if (!node) {
		return;
	}
	node->size = 1;
	if (node->l) {
		node->size += node->l->size;
	}
	if (node->r) {
		node->size += node->r->size;
	}
}

void Propagate(Node* node) {
	if (!node) {
		return;
	}

	node->val += node->lazy;
	if (node->l) {
		node->l->lazy += node->lazy;
	}
	if (node->r) {
		node->r->lazy += node->lazy;
	}
	node->lazy = 0;
}

void SplitDriver(Node* node, int key) {
	Propagate(node);
	if (!node) {
		return (void)(_aux_split_l = _aux_split_r = nullptr);
	}

	if (key-GetNodeSize(node->l)-1 >= 0) {
		SplitDriver(node->r,key-GetNodeSize(node->l)-1);
		node->r = _aux_split_l;
		_aux_split_l = node;
		UpdateNodeSize(node);
	}
	else {
		SplitDriver(node->l,key);
		node->l = _aux_split_r;
		_aux_split_r = node;
		UpdateNodeSize(node);
	}
}

// l < key, r >= key
inline std::pair<Node*, Node*> Split(Node* node, int key) {
	SplitDriver(node,key);
	return {_aux_split_l, _aux_split_r};
}

void MergeDriver(Node* a, Node* b) {
	Propagate(a);
	Propagate(b);

	if (!a) {
		return (void)(_aux_merge = b);
	}
	if (!b) {
		return (void)(_aux_merge = a);
	}

	if (a->prio > b->prio) {
		MergeDriver(a->r,b);
		a->r = _aux_merge;
		_aux_merge = a;
		UpdateNodeSize(a);
	}
	else {
		MergeDriver(a,b->l);
		b->l = _aux_merge;
		_aux_merge = b;
		UpdateNodeSize(b);
	}
}

inline Node* Merge(Node* a, Node* b) {
	MergeDriver(a,b);
	return _aux_merge;
}

Node* Insert(Node*& root, int pos, int val) {
	if (!root) {
		root = new Node(val);
		return root;
	}

	auto trees = Split(root, pos);
	return root = Merge(Merge(trees.first, new Node(val)), trees.second);
}

int GetKth(Node* node, int k, int skipped = 0) {
	Propagate(node);
	if (!node) {
		return -1;
	}

	int key = GetNodeSize(node->l) + skipped;
	if (key==k) {
		return node->val;
	}
	else if (key<k) {
		return GetKth(node->r,key+1);
	}
	else {
		return GetKth(node->l,skipped);
	}
}

int LowerBound(Node* node, int val, int skipped = 0) {
	Propagate(node);
	if (!node) {
		return 0x3f3f3f3f;
	}

	int key = GetNodeSize(node->l) + skipped;
	if (node->val>=val) {
		return std::min(key, LowerBound(node->l,val,skipped));
	}
	else {
		return LowerBound(node->r,val,key+1);
	}
}

int UpperBound(Node* node, int val, int skipped = 0) {
	Propagate(node);
	if (!node) {
		return 0x3f3f3f3f;
	}

	int key = GetNodeSize(node->l) + skipped;
	if (node->val>val) {
		return std::min(key, UpperBound(node->l,val,skipped));
	}
	else {
		return UpperBound(node->r,val,key+1);
	}
}

void Inorder(Node* node, int depth = 0) {
	Propagate(node);
	if (!node) {
		return;
	}

	Inorder(node->l,depth+1);
	std::cout << node->val << " ";
	Inorder(node->r,depth+1);

	if (!depth) {
		std::cout << "\n";
	}
}
}; // namespace Treap

int x, q;

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> x >> q;
	Treap::Node* root = nullptr;
	for (int i = 0, tmp; i < x; i++) {
		std::cin >> tmp;
		root = Treap::Insert(root, Treap::LowerBound(root, tmp), tmp);
	}

	//Treap::Inorder(root);
	while (q--) {
		char op;
		std::cin >> op;

		if (op=='C') {
			int l, r;
			std::cin >> l >> r;

			int le = std::min(x, Treap::LowerBound(root,l));
			int ri = std::min(x, Treap::UpperBound(root,r));
			std::cout << ri-le << "\n";
		}
		else {
			int k, m;
			std::cin >> k >> m;

#if 1
			int pos = Treap::LowerBound(root, m);
			auto trees = Treap::Split(root, pos);
			auto trees_right = Treap::Split(trees.second,k);

			Treap::Node* a = trees_right.first;
			if (a) {
				a->lazy += 1;
				Treap::Propagate(a);
			}
			Treap::Node* b = Treap::Merge(trees.first, trees_right.second);

			if (!a) {
				root = b;
				continue;
			}
			if (!b) {
				root = a;
				continue;
			}

			if (Treap::GetKth(a,0) > Treap::GetKth(b,0)) {
				std::swap(a,b);
			}

			Treap::Node* new_root = nullptr;
			int nodes_merged = 0;
			while (nodes_merged < x) {
				auto trees = Treap::Split(a, ((b) ? Treap::UpperBound(a, Treap::GetKth(b, 0))
				                                  : Treap::GetNodeSize(a)));
				nodes_merged += Treap::GetNodeSize(trees.first);
				new_root = Treap::Merge(new_root, trees.first);
				a = trees.second;
				std::swap(a,b);
			}

			root = new_root;
#endif
		}
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10