daily pastebin goal
25%
SHARE
TWEET

k-th biggest element O(1) manip

keverman Sep 13th, 2018 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. struct minimumpq
  4. {
  5.     bool operator()(const int &l, const int &r)
  6.     {
  7.         return l>r;
  8.     }
  9. };
  10.  
  11. int main()
  12. {
  13.     std::priority_queue<int>                              mxpq;
  14.     std::priority_queue<int, std::vector<int>, minimumpq> mnpq;
  15.  
  16.     int k;
  17.     std::cin >> k;
  18.  
  19.     while(true)
  20.     {
  21.         int t;
  22.         std::cin >> t;
  23.  
  24.         switch(t)
  25.         {
  26.         case 0:
  27.             exit(0);
  28.  
  29.         case 1:
  30.             std::cout << mxpq.top() << "\n";
  31.             break;
  32.  
  33.         case 2:
  34.             int n;
  35.             std::cin >> n;
  36.             mxpq.push(n);
  37.  
  38.             if(mxpq.size() == k + 1)
  39.             {
  40.                 mnpq.push(mxpq.top());
  41.                 mxpq.pop();
  42.             }
  43.             break;
  44.  
  45.         case 3:
  46.             mxpq.pop();
  47.  
  48.             if(!mnpq.empty())
  49.             {
  50.                 mxpq.push(mnpq.top());
  51.                 mnpq.pop();
  52.             }
  53.  
  54.             break;
  55.  
  56.         }
  57.     }
  58. }
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