daily pastebin goal
1%
SHARE
TWEET

Untitled

a guest Nov 20th, 2017 48 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //
  2. //  main.cpp
  3. //  3_2
  4. //
  5. //  Created by Артем Ямалутдинов on 12.11.17.
  6. //  Copyright © 2017 Артем Ямалутдинов. All rights reserved.
  7. //
  8.  
  9. #include <iostream>
  10.  
  11. struct CNode;
  12. using AVLTree = CNode*;
  13.  
  14. struct CNode {
  15.     CNode (int key): key(key), size(1), height(1), left(nullptr), right(nullptr) {}
  16.     int key;
  17.     int size; //Суммарный размер поддерева
  18.     int height; //Высота поддерева
  19.     AVLTree left;
  20.     AVLTree right;
  21. };
  22.  
  23. int height (AVLTree tree) {
  24.     return tree ? tree->height : 0;
  25. }
  26.  
  27. int balanceFactor(AVLTree tree) {
  28.     return height(tree->right) - height(tree->left);
  29. }
  30.  
  31. int fixSize(AVLTree tree) { //Восстанавливает значение размера поддерева
  32.     if (!tree) {
  33.         return 0;
  34.     }
  35.     if (tree->left && tree->right) {
  36.         return tree->left->size + tree->right->size + 1;
  37.     }
  38.     else if (tree->left || tree->right) {
  39.         return tree->left ? tree->left->size + 1 : tree->right->size + 1;
  40.     }
  41.     else {
  42.         return 1;
  43.     }
  44. }
  45.  
  46. void fixHeight(AVLTree tree) { //Восстанавливает значение высоты поддерева
  47.     int h_left = height(tree->left);
  48.     int h_right = height(tree->right);
  49.     tree->height = (h_left > h_right ? h_left : h_right) + 1;
  50.     tree->size = fixSize(tree);
  51. }
  52.  
  53. AVLTree rotateLeft (AVLTree tree) { //Малое левое вращение
  54.     AVLTree rightTree = tree->right;
  55.     tree->right = rightTree->left;
  56.     rightTree->left = tree;
  57.     fixHeight(tree);
  58.     fixHeight(rightTree);
  59.     return rightTree;
  60. }
  61.  
  62. AVLTree rotateRight (AVLTree tree) { //Малое правое вращение
  63.     AVLTree leftTree = tree->left;
  64.     tree->left = leftTree->right;
  65.     leftTree->right = tree;
  66.     fixHeight(tree);
  67.     fixHeight(leftTree);
  68.     return leftTree;
  69. }
  70.  
  71. AVLTree balanceTree (AVLTree tree) { //Балансировка дерева
  72.     fixHeight(tree);
  73.     if (balanceFactor(tree) == 2) {
  74.         if (balanceFactor(tree->right) < 0) {
  75.             tree->right = rotateRight(tree->right);
  76.         }
  77.         return rotateLeft(tree);
  78.     }
  79.     if (balanceFactor(tree) == -2) {
  80.         if (balanceFactor(tree->left) > 0) {
  81.             tree->left = rotateLeft(tree->left);
  82.         }
  83.         return rotateRight(tree);
  84.     }
  85.     return tree;
  86. }
  87.  
  88. AVLTree insert (AVLTree tree, int key) {
  89.     if (!tree) {
  90.         return new CNode(key);
  91.     }
  92.     if (key < tree->key) {
  93.         tree->left = insert(tree->left, key);
  94.     }
  95.     else {
  96.         tree->right = insert(tree->right, key);
  97.     }
  98.     return balanceTree(tree);
  99. }
  100.  
  101. AVLTree findMin (AVLTree tree) { //Поиск минимального элемента в данном поддереве
  102.     return tree->left ? findMin(tree -> left) : tree;
  103. }
  104.  
  105. AVLTree removeMin (AVLTree tree) {
  106.     if (tree->left == nullptr) {
  107.         return tree->right;
  108.     }
  109.     tree->left = removeMin(tree->left);
  110.     return balanceTree(tree);
  111. }
  112.  
  113.  
  114. AVLTree remove (AVLTree tree, int key) {
  115.     if (!tree) {
  116.         return nullptr;
  117.     }
  118.     if (tree->key > key) {
  119.         tree->left = remove(tree->left, key);
  120.     }
  121.     else if (tree->key < key) {
  122.         tree->right = remove(tree->right, key);
  123.     }
  124.     else {
  125.         AVLTree leftTree = tree->left;
  126.         AVLTree rightTree = tree->right;
  127.         delete tree;
  128.         if (!rightTree) {
  129.             return leftTree;
  130.         }
  131.         AVLTree min = findMin(rightTree);
  132.         min->right = removeMin(rightTree);
  133.         min->left = leftTree;
  134.         return balanceTree(min);
  135.     }
  136.     return balanceTree(tree);
  137. }
  138.  
  139. int getKStat(AVLTree tree, int k) {
  140.     AVLTree tmp_tree = tree;
  141.     while (tmp_tree) {
  142.         if (fixSize(tmp_tree->left) == k) {
  143.             return tmp_tree->key;
  144.         }
  145.         else if (fixSize(tmp_tree->left) > k) {
  146.             tmp_tree = tmp_tree->left;
  147.         }
  148.         else {
  149.             k -= (fixSize(tmp_tree->left) + 1);
  150.             tmp_tree = tmp_tree->right;
  151.         }
  152.     }
  153.     return -1;
  154. }
  155.  
  156. void deleteTree (AVLTree tree) {
  157.     if (!tree) {
  158.         return;
  159.     }
  160.     deleteTree(tree->left);
  161.     deleteTree(tree->right);
  162.     delete tree;
  163. }
  164.  
  165.  
  166. int main() {
  167.     int count = 0;
  168.     std::cin >> count;
  169.     int key = 0, kStat = 0;
  170.     AVLTree tree = nullptr;
  171.     for (int i = 0; i < count; ++i) {
  172.         std::cin >> key >> kStat;
  173.         if (key >= 0) {
  174.             tree = insert(tree, key);
  175.         }
  176.         else {
  177.             key *= -1;
  178.             tree = remove(tree, key);
  179.         }
  180.         std::cout << getKStat(tree, kStat) << std::endl;
  181.     }
  182.     deleteTree(tree);
  183.     return 0;
  184. }
RAW Paste Data
Top