SHARE
TWEET

Untitled

a guest Apr 21st, 2019 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <ctime>
  4. #include <vector>
  5. #include <string>
  6.  
  7. using namespace std;
  8.  
  9. struct TreapElement {
  10.     TreapElement(TreapElement *left, TreapElement *right, int cost, int y, int count)
  11.             : left(left), right(right), cost(cost), y(y), count(count) {
  12.         root = nullptr;
  13.         hasEmptyVertex = false;
  14.     }
  15.  
  16.     TreapElement() {
  17.         root = nullptr;
  18.         left = nullptr;
  19.         right = nullptr;
  20.     }
  21.  
  22.     virtual ~TreapElement() = default;
  23.  
  24.     TreapElement *left, *right, *root;
  25.     int y, count, cost;
  26.     bool hasEmptyVertex;
  27. };
  28.  
  29. void updateV(TreapElement *v) {
  30.     if (v != nullptr) {
  31.         v->count = (v->left == nullptr ? 0 : v->left->count) + (v->right == nullptr ? 0 : v->right->count) + 1;
  32.         v->hasEmptyVertex = (v->cost == 0
  33.                              || (v->left != nullptr && v->left->hasEmptyVertex)
  34.                              || (v->right != nullptr && v->right->hasEmptyVertex));
  35.     }
  36. }
  37.  
  38. TreapElement **split(TreapElement *v, int pseudoKey) {
  39.     TreapElement *leftTreap = nullptr;
  40.     TreapElement *rightTreap = nullptr;
  41.     TreapElement *middleTreap = nullptr;
  42.     auto **tempTreaps = new TreapElement*[2];
  43.     if (v == nullptr) {
  44.         tempTreaps[0] = nullptr;
  45.         tempTreaps[1] = nullptr;
  46.         return tempTreaps;
  47.     }
  48.     int currentIndex = (v->left != nullptr ? v->left->count : 0) + 1;
  49.     if (pseudoKey >= currentIndex) {
  50.         if (v->right == nullptr) {
  51.             rightTreap = nullptr;
  52.         } else {
  53.             tempTreaps = split(v->right, pseudoKey - currentIndex);
  54.             middleTreap = tempTreaps[0];
  55.             rightTreap = tempTreaps[1];
  56.         }
  57.         leftTreap = new TreapElement(v->left, middleTreap, v->cost, v->y, v->count);
  58.         updateV(leftTreap);
  59.     } else {
  60.         if (v->left == nullptr) {
  61.             leftTreap = nullptr;
  62.         } else {
  63.             tempTreaps = split(v->left, pseudoKey);
  64.             leftTreap = tempTreaps[0];
  65.             middleTreap = tempTreaps[1];
  66.         }
  67.         rightTreap = new TreapElement(middleTreap, v->right, v->cost, v->y, v->count);
  68.         updateV(rightTreap);
  69.     }
  70.     tempTreaps[0] = leftTreap;
  71.     tempTreaps[1] = rightTreap;
  72.     return tempTreaps;
  73. }
  74.  
  75. TreapElement *merge(TreapElement *leftTreap, TreapElement *rightTreap) {
  76.     if (leftTreap == nullptr) {
  77.         updateV(rightTreap);
  78.         return rightTreap;
  79.     }
  80.     if (rightTreap == nullptr) {
  81.         updateV(leftTreap);
  82.         return leftTreap;
  83.     }
  84.     if (leftTreap->y > rightTreap->y) {
  85.         leftTreap->right = merge(leftTreap->right, rightTreap);
  86.         updateV(leftTreap);
  87.         return leftTreap;
  88.     } else {
  89.         rightTreap->left = merge(leftTreap, rightTreap->left);
  90.         updateV(rightTreap);
  91.         return rightTreap;
  92.     }
  93. }
  94.  
  95. TreapElement *insert(TreapElement *v, int position, int cost, int value) {
  96.     TreapElement **tempTreaps = split(v, position);
  97.     auto *middleTreap = new TreapElement(nullptr, nullptr, cost, value, 1);
  98.     return merge(merge(tempTreaps[0], middleTreap), tempTreaps[1]);
  99. }
  100.  
  101. TreapElement *remove(TreapElement *v, int position) {
  102.     TreapElement **tempTreapsOne = split(v, position);
  103.     TreapElement **tempTreapsTwo = split(tempTreapsOne[1], 1);
  104.     return merge(tempTreapsOne[0], tempTreapsTwo[1]);
  105. }
  106.  
  107. int findEmptyVertexWithLowestPosition(TreapElement *v, int position) {
  108.     if (v->left != nullptr && v->left->hasEmptyVertex) {
  109.         return findEmptyVertexWithLowestPosition(v->left, position);
  110.     } else if (v->cost == 0) {
  111.         return position + (v->left != nullptr ? v->left->count : 0);
  112.     } else {
  113.         return findEmptyVertexWithLowestPosition(v->right, position + (v->left != nullptr ? v->left->count : 0) + 1);
  114.     }
  115. }
  116.  
  117. vector<int> costs;
  118.  
  119. void inOrderTraversal(TreapElement *v) {
  120.     if (v != nullptr) {
  121.         inOrderTraversal(v->left);
  122.         costs.insert(costs.begin(), v->cost);
  123.         inOrderTraversal(v->right);
  124.     }
  125. }
  126.  
  127. int main() {
  128.     int n, m;
  129.     cin >> n >> m;
  130.     auto treap = new TreapElement();
  131.     srand(time(nullptr));
  132.  
  133.     for (int i = 0; i <= n + m; ++i) {
  134.         treap->root = insert(treap->root, i, 0, rand());
  135.     }
  136.  
  137.     for (int i = 0; i < n; ++i) {
  138.         int x;
  139.         cin >> x;
  140.         x -= 1;
  141.         treap->root = insert(treap->root, x, i + 1, rand());
  142.         TreapElement **tempTreaps = split(treap->root, ++x);
  143.         int position = findEmptyVertexWithLowestPosition(tempTreaps[1], x);
  144.         treap->root = remove(treap->root, position);
  145.     }
  146.  
  147.     inOrderTraversal(treap->root);
  148.  
  149.     int i = 0;
  150.     while (costs[i] == 0) {
  151.         costs.erase(costs.begin());
  152.     }
  153.  
  154.     string result;
  155.     cout << costs.size() << endl;
  156.     while (costs.size() > 1) {
  157.         result = " " + to_string(costs[0]) + result;
  158.         costs.erase(costs.begin());
  159.     }
  160.     result = to_string(costs[0]) + result;
  161.     cout << result;
  162.  
  163.     delete treap;
  164.  
  165.     return 0;
  166. }
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