fork(2) download 
  1. // uppi.cc -*- mode:c++, compile-command:"g++ -Wall -Wextra -pedantic -std=c++0x uppi.cc -o uppi && ./uppi" -*-
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <set>
  6. #include <cassert>
  7. #include <iterator>
  8.  
  9. template <typename T>
  10. class median_set {
  11. public:
  12.   std::multiset<T> below, above;
  13.  
  14.   // O(log N)
  15.   void rebalance()
  16.   {
  17.     int diff = above.size() - below.size();
  18.     if (diff > 0) {
  19.       below.insert(*above.begin());
  20.       above.erase(above.begin());
  21.     } else if (diff < -1) {
  22.       above.insert(*below.rbegin());
  23.       below.erase(below.find(*below.rbegin()));
  24.     }
  25.   }
  26.  
  27. public:
  28.   // O(1)
  29.   bool empty() const { return below.empty() && above.empty(); }
  30.  
  31.   // O(1)
  32.   T const& median() const
  33.   {
  34.     assert(!empty());
  35.     return *below.rbegin();
  36.   }
  37.  
  38.   // O(log N)
  39.   void insert(T const& value)
  40.   {
  41.     if (!empty() && value > median())
  42.       above.insert(value);
  43.     else
  44.       below.insert(value);
  45.     rebalance();
  46.   }
  47.  
  48.   // O(log N)
  49.   void erase(T const& value)
  50.   {
  51.     if (value > median())
  52.       above.erase(above.find(value));
  53.     else
  54.       below.erase(below.find(value));
  55.     rebalance();
  56.   }
  57. };
  58.  
  59. int main()
  60. {
  61.   median_set<int> ms;
  62.   std::vector<int> v;
  63.   srand(0);
  64.   for (int i=0; i<100000; ++i) {
  65.     bool remove = !(rand()%3);
  66.     if (remove && !v.empty()) {
  67.       unsigned rnd = rand();
  68.       int idx = rnd%v.size();
  69.       ms.erase(v[idx]);
  70.       v.erase(v.begin()+idx);
  71.     } else {
  72.       int value = rand();
  73.       ms.insert(value);
  74.       v.push_back(value);
  75.     }
  76.  
  77.     if (!v.empty()) {
  78.       std::sort(v.begin(), v.end());
  79.       int median1 = v[(v.size()-1)/2];
  80.       int median2 = ms.median();
  81.       assert(median1 == median2);
  82.     }
  83.   }
  84. }
  85.  
Time limit exceeded #stdin #stdout 5s 3316KB
comments ()
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/uK7h48
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!