Advertisement
Guest User

Untitled

a guest
Nov 17th, 2019
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.58 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement