Apkawa

Untitled

Sep 19th, 2021
786
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ull unsigned ll
  4. #define ld long double
  5. #define be(a) a.begin(), a.end()
  6. #define L(x, n) for (int x = 0; x < n; ++x)
  7. #define F first
  8. #define S second
  9. #pragma GCC optimize("Ofast")
  10. using namespace std;
  11.  
  12. void sift_down(int i, vector <int> &a) {
  13.     int j;
  14.     bool x = int(floor(log2(i + 1)))%2;
  15.     while (2*i + 1 < a.size()) {
  16.         j = 2*i + 1;
  17.         if (j + 1 < a.size() && (a[j + 1] < a[j])^x)
  18.             ++j;
  19.         for (int k = i*4 + 3; k < min(int(a.size()), i*4 + 7); ++k)
  20.             if ((a[k] < a[j])^x)
  21.                 j = k;
  22.         if (j >= 4*i + 3) {
  23.             if ((a[j] < a[i])^x)
  24.                 swap(a[i], a[j]);
  25.             if ((a[j] > a[(j - 1) >> 1])^x)
  26.                 swap(a[j], a[(j - 1) >> 1]);
  27.             i = j;
  28.         }
  29.         else {
  30.             if ((a[j] < a[i])^x)
  31.                 swap(a[i], a[j]);
  32.             break;
  33.         }
  34.     }
  35. }
  36.  
  37. void sift_up(int i, vector <int> &a) {
  38.     while (i > 2) {
  39.         if (int(floor(log2(i + 1)))%2 == 0)
  40.             if (a[i] > a[(i - 1) >> 1])
  41.                 swap(a[i], a[(i - 1) >> 1]),
  42.                 i = (i - 1) >> 1;
  43.             else
  44.                 if (i > 2 && a[i] < a[(((i - 1) >> 1) - 1) >> 1])
  45.                     swap(a[i], a[(((i - 1) >> 1) - 1) >> 1]),
  46.                     i = (((i - 1) >> 1) - 1) >> 1;
  47.                 else
  48.                     break;
  49.         else
  50.             if (a[i] < a[(i - 1) >> 1])
  51.                 swap(a[i], a[(i - 1) >> 1]),
  52.                 i = (i - 1) >> 1;
  53.             else
  54.                 if (i > 2 && a[i] > a[(((i - 1) >> 1) - 1) >> 1])
  55.                     swap(a[i], a[(((i - 1) >> 1) - 1) >> 1]),
  56.                     i = (((i - 1) >> 1) - 1) >> 1;
  57.                 else
  58.                     break;
  59.     }
  60. }
  61.  
  62. int remove(int i, vector <int> &a) {
  63.     int t = a[i];
  64.     swap(a[i], a.back());
  65.     a.erase(a.end() - 1);
  66.     sift_down(i, a);
  67.     return t;
  68. }
  69.  
  70. void insert(int v, vector <int> &a) {
  71.     a.push_back(v);
  72.     sift_up(a.size() - 1, a);
  73. }
  74.  
  75. int main() {
  76.     freopen("input.txt", "r", stdin);
  77.     //freopen("output.txt", "w", stdout);
  78.     ios_base::sync_with_stdio(0);
  79.     cin.tie(0);
  80.  
  81.     vector <int> a;
  82.     string op;
  83.  
  84.     while (cin >> op) {
  85.         if (op == "ins") {
  86.             int x;
  87.             cin >> x;
  88.             insert(x, a);
  89.         }
  90.         if (op == "max")
  91.             if (a.size() > 2)
  92.                 if (a[1] > a[2])
  93.                     cout << remove(1, a) << endl;
  94.                 else
  95.                     cout << remove(2, a) << endl;
  96.             else
  97.                 if (a.size() == 1 || a[0] > a[1])
  98.                     cout << remove(0, a) << endl;
  99.                 else
  100.                     cout << remove(1, a) << endl;
  101.         if (op == "min")
  102.             cout << remove(0, a) << endl;
  103.         cout << "##### ";
  104.         for (int i : a)
  105.             cout << i << ' ';
  106.         cout << endl;
  107.     }
  108.  
  109.     return 0;
  110. }
  111.  
RAW Paste Data