SHARE
TWEET

Untitled

a guest Dec 14th, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. //#include "optimization.h"
  3. using namespace std;
  4. int hmax[100001], hmin[100001], delmin[100001], delmax[100001];
  5. int n1 = 0, n2 = 0, n3 = 0, n4 = 0;
  6. int i, l = 2*i;
  7. int countmin, countmax;
  8.  
  9. int GetMin_hmin() {
  10.     return hmin[1];
  11. }
  12. int GetMin_delmax() { return delmax[1]; }
  13. int GetMax_hmax() { return hmax[1]; }
  14. int GetMax_delmin() { return delmin[1]; }
  15.  
  16. void siftDown_hmax(int i) {
  17.     while (1) {
  18.         if (l + 1 <= n1 && hmax[l + 1] > hmax[l])
  19.             l++;
  20.         if (l >= n1 && hmax[l] < hmax[i])
  21.             break;
  22.         swap(hmax[l], hmax[i]);
  23.         i = l;
  24.     }
  25. }
  26. void siftDown_hmin(int i) {
  27.     while (1) {
  28.         //int l = 2 * i;
  29.         if (l + 1 <= n2 && hmin[l + 1] < hmin[l]) l++;
  30.         if (!(l <= n2 && hmin[l] < hmin[i])) break;
  31.         swap(hmin[l], hmin[i]);
  32.         i = l;
  33.     }
  34. }
  35. void siftDown_delmin(int i) {
  36.     while (1) {
  37.         int l = 2 * i;
  38.         if (l + 1 <= n3 && delmin[l + 1] > delmin[l]) l++;
  39.         if (!(l <= n3 && delmin[l] > delmin[i])) break;
  40.         swap(delmin[l], delmin[i]);
  41.         i = l;
  42.     }
  43. }
  44. void siftDown_delmax(int i) {
  45.     while (1) {
  46.         //int l = 2 * i;
  47.         if (l + 1 <= n4 && delmax[l + 1] < delmax[l]) l++;
  48.         if (!(l <= n4 && delmax[l] < delmax[i])) break;
  49.         swap(delmax[l], delmax[i]);
  50.         i = l;
  51.     }
  52. }
  53. void ExtractMin_hmin() {
  54.     swap(hmin[1], hmin[n2--]);
  55.     siftDown_hmin(1);
  56. }
  57. void ExtractMin_delmax() {
  58.     swap(delmax[1], delmax[n4--]);
  59.     siftDown_delmax(1);
  60. }
  61. void ExtractMax_hmax() {
  62.     swap(hmax[1], hmax[n1--]);
  63.     siftDown_hmax(1);
  64. }
  65. void ExtractMax_delmin() {
  66.     swap(delmin[1], delmin[n3--]);
  67.     siftDown_delmin(1);
  68. }
  69.  
  70. void siftUp_hmin(int i) {
  71.     while (i > 1 && hmin[i / 2] > hmin[i]) {
  72.         swap(hmin[i], hmin[i / 2]);
  73.         i /= 2;
  74.     }
  75. }
  76. void siftUp_hmax(int i) {
  77.     while (i > 1 && hmax[i / 2] < hmax[i]) {
  78.         swap(hmax[i], hmax[i / 2]);
  79.         i /= 2;
  80.     }
  81. }
  82. void siftUp_delmax(int i) {
  83.     while (i > 1 && delmax[i / 2] > delmax[i]) {
  84.         swap(delmax[i], delmax[i / 2]);
  85.         i /= 2;
  86.     }
  87. }
  88. void siftUp_delmin(int i) {
  89.     while (i > 1 && delmin[i / 2] < delmin[i]) {
  90.         swap(delmin[i], delmin[i / 2]);
  91.         i /= 2;
  92.     }
  93. }
  94.  
  95. void Add_delmax(int x) {
  96.     delmax[++n4] = x;
  97.     siftUp_delmax(n4);
  98. }
  99. void Add_delmin(int x) {
  100.     delmin[++n3] = x;
  101.     siftUp_delmin(n3);
  102. }
  103.  
  104. int GetMax() {
  105.     if (countmin) {
  106.         while (GetMax_hmax() == GetMax_delmin()) {
  107.             ExtractMax_hmax();
  108.             ExtractMax_delmin();
  109.             countmin--;
  110.             if (!countmin) break;
  111.         }
  112.     }
  113.     int x = GetMax_hmax();
  114.     Add_delmax(x);
  115.     countmax++;
  116.     ExtractMax_hmax();
  117.     return x;
  118. }
  119. int GetMin() {
  120.     if (countmax) {
  121.         while (GetMin_hmin() == GetMin_delmax()) {
  122.             ExtractMin_hmin();
  123.             ExtractMin_delmax();
  124.             countmax--;
  125.             if (!countmax) break;
  126.         }
  127.     }
  128.     int x = GetMin_hmin();
  129.     Add_delmin(x);
  130.     countmin++;
  131.     ExtractMin_hmin();
  132.     return x;
  133. }
  134.  
  135. void Add(int x) {
  136.     hmax[++n1] = x;
  137.     siftUp_hmax(n1);
  138.     hmin[++n2] = x;
  139.     siftUp_hmin(n2);
  140. }
  141.  
  142. int main() {
  143.     int n;
  144.     cin >> n; //n = readInt();
  145.     char input[30];
  146.     for (int j = 0; j < n; j++) {
  147.         int i = 0;
  148.         cin >> input[i]; // = readChar();
  149.         int num;
  150.         if (input[i] == 'I') {
  151.             while (input[i] != '(') {
  152.                 i++;
  153.                 cin >> input[i]; // = readChar();
  154.             }
  155.             i++;
  156.             cin >> input[i]; // = readChar();
  157.             num = 0;
  158.             while (input[i] != ')') {
  159.                 num *= 10;
  160.                 num += input[i] - '0';
  161.                 cin >> input[i]; // = readChar();
  162.             }
  163.             Add(num);
  164.         }
  165.         else {
  166.             while (input[i] != 'M') {
  167.                 i++;
  168.                 cin >> input[i]; // = readChar();
  169.             }
  170.             i++;
  171.             cin >> input[i]; // = readChar();
  172.             if (input[i] == 'a') {
  173.                 cin >> input[i]; // = readChar();
  174.                 cout << GetMax() << '\n';
  175.             }
  176.             else {
  177.                 cin >> input[i]; // = readChar();
  178.                 cout << GetMin() << '\n';
  179.             }
  180.         }
  181.     }
  182.     return 0;
  183. }
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