Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- class Treap{
- public:
- int x;
- int y;
- Treap* left;
- Treap* right;
- Treap(int x, int y, Treap* left, Treap* right) {
- this->x = x;
- this->y = y;
- this->left = left;
- this->right = right;
- }
- ~Treap() {
- if (this->left != nullptr) {
- delete this->left;
- }
- if (this->right != nullptr) {
- delete this->right;
- }
- }
- Treap* Merge(Treap* firstTree, Treap* secondTree) {
- if (firstTree == nullptr)
- return secondTree;
- if (secondTree == nullptr)
- return firstTree;
- if (firstTree->y > secondTree->y) {
- firstTree->right = Merge(firstTree->right, secondTree);
- return firstTree;
- } else {
- secondTree->left = Merge(firstTree, secondTree->left);
- return secondTree;
- }
- }
- void Split(int x, Treap*& outLeft, Treap*& outRight) {
- Treap* newTreap = nullptr;
- if (this->x <= x) {
- if (this->right == nullptr)
- outRight = nullptr;
- else this->right->Split(x, newTreap, outRight);
- this->right = newTreap;
- outLeft = this;
- } else {
- if (this->left == nullptr)
- outLeft = nullptr;
- else this->left->Split(x, outLeft, newTreap);
- this->left = newTreap;
- outRight = this;
- }
- }
- Treap* Insert(int x, int y) {
- Treap* outLeft = nullptr;
- Treap* outRight = nullptr;
- this->Split(x, outLeft, outRight);
- Treap* newNode = new Treap(x, y, nullptr, nullptr);
- return this->Merge(this->Merge(outLeft, newNode), outRight);
- }
- int Depth(Treap* tp) {
- int lDepth = 0;
- int rDepth = 0;
- if (tp->left != nullptr)
- lDepth = Depth(tp->left);
- if (tp->right != nullptr)
- rDepth = Depth(tp->right);
- return 1 + ( lDepth > rDepth ? lDepth : rDepth);
- }
- };
- class Elem{
- private:
- int x;
- Elem* left;
- Elem* right;
- public:
- Elem(int x) {
- this->x = x;
- this->left = nullptr;
- this->right = nullptr;
- }
- ~Elem() {
- }
- int GetVal() {
- return this->x;
- }
- void SetLeft(Elem* left) {
- this->left = left;
- }
- void SetRight(Elem* right) {
- this->right = right;
- }
- Elem* GetLeft() {
- return this->left;
- }
- Elem* GetRight() {
- return this->right;
- }
- };
- class BinTree{
- private:
- Elem* root;
- Elem* Add(Elem* node, int x) {
- if (node == nullptr) {
- return new Elem(x);
- } else if (node->GetVal() < x) {
- node->SetRight( Add(node->GetRight(), x) );
- } else {
- node->SetLeft( Add(node->GetLeft(),x) );
- }
- return node;
- }
- void DeleteTree(Elem* node) {
- if (node != nullptr) {
- if ( node->GetLeft() != nullptr) {
- DeleteTree(node->GetLeft());
- }
- if ( node->GetRight() != nullptr) {
- DeleteTree(node->GetRight());
- }
- delete node;
- }
- }
- public:
- BinTree() {
- this->root = nullptr;
- }
- ~BinTree() {
- DeleteTree(this->root);
- }
- Elem* GetRoot() {
- return this->root;
- }
- void Insert(int x) {
- this->root = this->Add(this->root, x);
- }
- void InorderTraversal(Elem* node) {
- if (node != nullptr) {
- if (node->GetLeft() != nullptr) {
- InorderTraversal(node->GetLeft());
- }
- std::cout << node->GetVal() << " ";
- if (node->GetRight() != nullptr) {
- InorderTraversal(node->GetRight());
- }
- }
- }
- int Depth(Elem* t) {
- int lDepth = 0;
- int rDepth = 0;
- if (t->GetLeft() != nullptr)
- lDepth = Depth(t->GetLeft());
- if (t->GetRight() != nullptr)
- rDepth = Depth(t->GetRight());
- return 1 + ( lDepth > rDepth ? lDepth : rDepth);
- }
- };
- int main() {
- int n;
- cin >> n;
- int x, y;
- cin >> x >> y;
- Treap* tp = new Treap(x, y, nullptr, nullptr);
- BinTree* bt = new BinTree();
- bt->Insert(x);
- for (int i = 1; i < n; i++) {
- cin >> x >> y;
- tp = tp->Insert(x, y);
- bt->Insert(x);
- }
- std::cout << bt->Depth(bt->GetRoot()) - tp->Depth(tp) << std::endl;
- delete bt;
- delete tp;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement