Advertisement
Guest User

Untitled

a guest
Dec 17th, 2018
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.62 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int k = 2;
  5. int mas[2000001];
  6. int r = 0;
  7.  
  8. void Shift_Up(int pos) {
  9.     if (pos == 0) {
  10.         return;
  11.     }
  12.     if (mas[pos] < mas[(pos - 1) / k]) {
  13.         swap(mas[pos], mas[(pos - 1) / k]);
  14.         Shift_Up((pos - 1) / k);
  15.     }
  16. }
  17. void Shift_Down(int pos) {
  18.     if (pos * k + 1 >= r) {
  19.         return;
  20.     }
  21.     int min_value = mas[pos * k + 1];
  22.     int pos_value = 1;
  23.     for (int i = 2; i <= k; ++i) {
  24.         if (pos * k + i < r && mas[pos * k + i] < min_value) {
  25.             min_value = mas[pos * k + i];
  26.             pos_value = i;
  27.         }
  28.     }
  29.     swap(mas[pos], mas[pos * k + pos_value]);
  30.     Shift_Down(pos * k + pos_value);
  31. }
  32.  
  33. void insert(int x) {
  34.     mas[r] = x;
  35.     r++;
  36.     Shift_Up(r - 1);
  37. }
  38. int get_min() {
  39.     return mas[0];
  40. }
  41. int size() {
  42.     return r;
  43. }
  44. void extract_min() {
  45.     --r;
  46.     swap(mas[0], mas[r]);
  47.     Shift_Down(0);
  48. }
  49.  
  50. vector <pair <string, int> > ans;
  51.  
  52. int main() {
  53.     ios_base::sync_with_stdio(0);
  54.     cin.tie(nullptr);
  55.     int n;
  56.     cin >> n;
  57.     for (int i = 0; i < n; ++i) {
  58.         string s;
  59.         cin >> s;
  60.         if (s == "insert") {
  61.             int x;
  62.             cin >> x;
  63.             insert(x);
  64.             ans.push_back({"insert", x});
  65.             continue;
  66.         }
  67.         if (s == "removeMin") {
  68.             if (size() == 0) {
  69.                 ans.push_back({"insert", 1});
  70.                 insert(1);
  71.             }
  72.             extract_min();
  73.             ans.push_back({"removeMin", 0});
  74.             continue;
  75.         }
  76.         if (s == "getMin") {
  77.             int x;
  78.             cin >> x;
  79.             if (size() == 0) {
  80.                 ans.push_back({"insert", x});
  81.                 insert(x);
  82.                 ans.push_back({"getMin", x});
  83.                 continue;
  84.             }
  85.             while (size() > 0 && get_min() < x) {
  86.                 extract_min();
  87.                 ans.push_back({"removeMin", 0});
  88.             }
  89.             if (size() == 0) {
  90.                 ans.push_back({"insert", x});
  91.                 insert(x);
  92.                 ans.push_back({"getMin", x});
  93.                 continue;
  94.             }
  95.             if (get_min() == x) {
  96.                 ans.push_back({"getMin", x});
  97.                 continue;
  98.             }
  99.             ans.push_back({"insert", x});
  100.             insert(x);
  101.             ans.push_back({"getMin", x});
  102.         }
  103.     }
  104.     cout << ans.size() << endl;
  105.     for (auto i : ans) {
  106.         cout << i.first << ' ';
  107.         if (i.first != "removeMin") {
  108.             cout << i.second;
  109.         }
  110.         cout << '\n';
  111.     }
  112.     return 0;
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement