SHARE
TWEET

Untitled

a guest Nov 17th, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. class Treap{
  6. public:
  7.     int x;
  8.     int y;
  9.     Treap* left;
  10.     Treap* right;
  11.     Treap(int x, int y, Treap* left, Treap* right) {
  12.         this->x = x;
  13.         this->y = y;
  14.         this->left = left;
  15.         this->right = right;
  16.     }
  17.     ~Treap() {
  18.         if (this->left != nullptr) {
  19.             delete this->left;
  20.         }
  21.         if (this->right != nullptr) {
  22.             delete this->right;
  23.         }
  24.     }
  25.     Treap* Merge(Treap* firstTree, Treap* secondTree) {
  26.         if (firstTree == nullptr)
  27.             return secondTree;
  28.         if (secondTree == nullptr)
  29.             return firstTree;
  30.         if (firstTree->y > secondTree->y) {
  31.             firstTree->right = Merge(firstTree->right, secondTree);
  32.             return firstTree;
  33.         } else {
  34.             secondTree->left = Merge(firstTree, secondTree->left);
  35.             return secondTree;
  36.         }
  37.     }
  38.     void Split(int x, Treap*& outLeft, Treap*& outRight) {
  39.         Treap* newTreap = nullptr;
  40.         if (this->x <= x) {
  41.             if (this->right == nullptr)
  42.                 outRight = nullptr;
  43.             else this->right->Split(x, newTreap, outRight);
  44.             this->right = newTreap;
  45.             outLeft = this;
  46.         } else {
  47.             if (this->left == nullptr)
  48.                 outLeft = nullptr;
  49.             else this->left->Split(x, outLeft, newTreap);
  50.             this->left = newTreap;
  51.             outRight = this;
  52.         }
  53.     }
  54.     Treap* Insert(int x, int y) {
  55.         Treap* outLeft = nullptr;
  56.         Treap* outRight = nullptr;
  57.         this->Split(x, outLeft, outRight);
  58.         Treap* newNode = new Treap(x, y, nullptr, nullptr);
  59.         return this->Merge(this->Merge(outLeft, newNode), outRight);
  60.     }
  61.     int Depth(Treap* tp) {
  62.         int lDepth = 0;
  63.         int rDepth = 0;
  64.         if (tp->left != nullptr)
  65.             lDepth = Depth(tp->left);
  66.         if (tp->right != nullptr)
  67.             rDepth = Depth(tp->right);
  68.         return 1 + ( lDepth > rDepth ? lDepth : rDepth);
  69.     }
  70. };
  71.  
  72. class Elem{
  73. private:
  74.     int x;
  75.     Elem* left;
  76.     Elem* right;
  77. public:
  78.     Elem(int x) {
  79.         this->x = x;
  80.         this->left = nullptr;
  81.         this->right = nullptr;
  82.     }
  83.     ~Elem() {
  84.  
  85.     }
  86.     int GetVal() {
  87.         return this->x;
  88.     }
  89.     void SetLeft(Elem* left) {
  90.         this->left = left;
  91.     }
  92.     void SetRight(Elem* right) {
  93.         this->right = right;
  94.     }
  95.     Elem* GetLeft() {
  96.         return this->left;
  97.     }
  98.     Elem* GetRight() {
  99.         return this->right;
  100.     }
  101. };
  102. class BinTree{
  103. private:
  104.     Elem* root;
  105.     Elem* Add(Elem* node, int x) {
  106.         if (node == nullptr) {
  107.             return new Elem(x);
  108.         } else if (node->GetVal() < x) {
  109.             node->SetRight( Add(node->GetRight(), x) );
  110.         } else {
  111.             node->SetLeft( Add(node->GetLeft(),x) );
  112.         }
  113.         return node;
  114.     }
  115.     void DeleteTree(Elem* node) {
  116.         if (node != nullptr) {
  117.             if ( node->GetLeft() != nullptr) {
  118.                 DeleteTree(node->GetLeft());
  119.             }
  120.             if ( node->GetRight() != nullptr) {
  121.                 DeleteTree(node->GetRight());
  122.             }
  123.             delete node;
  124.         }
  125.     }
  126. public:
  127.     BinTree() {
  128.         this->root = nullptr;
  129.     }
  130.     ~BinTree() {
  131.         DeleteTree(this->root);
  132.     }
  133.     Elem* GetRoot() {
  134.         return this->root;
  135.     }
  136.     void Insert(int x) {
  137.         this->root = this->Add(this->root, x);
  138.     }
  139.     void InorderTraversal(Elem* node) {
  140.         if (node != nullptr) {
  141.  
  142.             if (node->GetLeft() != nullptr) {
  143.                 InorderTraversal(node->GetLeft());
  144.             }
  145.             std::cout << node->GetVal() << " ";
  146.             if (node->GetRight() != nullptr) {
  147.                 InorderTraversal(node->GetRight());
  148.             }
  149.         }
  150.     }
  151.     int Depth(Elem* t) {
  152.         int lDepth = 0;
  153.         int rDepth = 0;
  154.         if (t->GetLeft() != nullptr)
  155.             lDepth = Depth(t->GetLeft());
  156.         if (t->GetRight() != nullptr)
  157.             rDepth = Depth(t->GetRight());
  158.         return 1 + ( lDepth > rDepth ? lDepth : rDepth);
  159.     }
  160. };
  161.  
  162. int main() {
  163.     int n;
  164.     cin >> n;
  165.     int x, y;
  166.     cin >> x >> y;
  167.     Treap* tp = new Treap(x, y, nullptr, nullptr);
  168.     BinTree* bt = new BinTree();
  169.     bt->Insert(x);
  170.     for (int i = 1; i < n; i++) {
  171.         cin >> x >> y;
  172.         tp = tp->Insert(x, y);
  173.         bt->Insert(x);
  174.     }
  175.  
  176.     std::cout <<  bt->Depth(bt->GetRoot()) - tp->Depth(tp) << std::endl;
  177.  
  178.     delete bt;
  179.     delete tp;
  180.     return 0;
  181. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top