Apkawa

Untitled

Sep 19th, 2021
789
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, bool x) {
  13.     int j;
  14.     while (2*i + 1 < a.size()) {
  15.         j = 2*i + 1;
  16.         if (j + 1 < a.size() && (a[j + 1] < a[j])^x)
  17.             ++j;
  18.         if (a[i] == a[j] || (a[i] < a[j])^x)
  19.             break;
  20.         swap(a[i], a[j]);
  21.         i = j;
  22.     }
  23. }
  24.  
  25. void sift_up(int i, vector <int> &a, bool x) {
  26.     while (i && (a[i] < a[(i - 1) >> 1])^x)
  27.         swap(a[i], a[(i - 1) >> 1]),
  28.         i = (i - 1) >> 1;
  29. }
  30.  
  31. int remove(vector <int> &a, bool x) {
  32.     int t = a[0];
  33.     swap(a[0], a.back());
  34.     a.erase(a.end() - 1);
  35.     sift_down(0, a, x);
  36.     return t;
  37. }
  38.  
  39. void insert(int v, vector <int> &a, bool x) {
  40.     a.push_back(v);
  41.     sift_up(a.size() - 1, a, x);
  42. }
  43.  
  44. int main() {
  45.     freopen("input.txt", "r", stdin);
  46.     //freopen("output.txt", "w", stdout);
  47.     ios_base::sync_with_stdio(0);
  48.     cin.tie(0);
  49.  
  50.     vector <int> a, b;
  51.     string op;
  52.     while (cin >> op) {
  53.         if (op == "ins") {
  54.             int x;
  55.             cin >> x;
  56.             if (a.size())
  57.                 if (x > a[0])
  58.                     insert(x, a, 0);
  59.                 else
  60.                     insert(x, b, 1);
  61.             else
  62.                 insert(x, b, 1);
  63.             if (a.size() > b.size())
  64.                 insert(remove(a, 0), b, 1);
  65.             else
  66.                 if (a.size() + 1 < b.size())
  67.                     insert(remove(b, 1), a, 0);
  68.         }
  69.         if (op == "med")
  70.             cout << b[0] << endl;
  71.         if (op == "remove_med")
  72.             cout << remove(b, 1) << endl;
  73.     }
  74.  
  75.     return 0;
  76. }
  77.  
RAW Paste Data