c++(404ms 78%) queue and set
Runtime: 404 ms, faster than 78.26% of C++ online submissions for Finding MK Average.\nMemory Usage: 146 MB, less than 62.50% of C++ online submissions for Find
Runtime: 404 ms, faster than 78.26% of C++ online submissions for Finding MK Average.\nMemory Usage: 146 MB, less than 62.50% of C++ online submissions for Finding MK Average.\n**General idea :**\n**1.** create queue with current of elements {element, id of element in stream} \n**2.** while size of queue less than **m** only put elements in queue\n**3.** one time whan size of queue will be equal **m** sort all elements from queue and put all elements into 3 sets : **mini** , **midi**, **maxi** , where mini contain first k elements, midi - next n( n = m - k - k) elements and maxi contain last k elements. And calculate sum of **midi** elements\n\n**from step 3 will repeat :**\n**1** delete old element from queue and from mini or midi or maxi\n**2** after deleting always will be reconstruct our mini, midi and maxi in such manner : mini - k elements, midi - n-1 elements and maxi - k elements (will support mini and maxi with maximal size)\n**3** put new element into mini , midi or maxi (for all theese steps recalculate sum)\n```\nclass MKAverage {\npublic:\n  set<pair<int,int>> mini,midi,maxi;\n  queue<pair<int,int>> q;\n  int id, k, n, m, lim, sum;\n  \n  MKAverage(int m, int k) {\n    sum = id = 0, this->k = k, this->m = m, n = m - k - k, lim = m + 1;      \n  }\n    \n  void addElement(int num) {\n    q.push({num, ++id});\n    \n    if(q.size() == lim){\n      auto p = q.front(); q.pop();\n      \n      if(mini.count(p)) mini.erase(p);                      //delete old\n      else if(maxi.count(p)) maxi.erase(p);\n      else midi.erase(p), sum -= p.first;\n      \n      if(mini.size() != k){                                 //replace\n        mini.insert(*midi.begin()), sum -= midi.begin()->first;\n        midi.erase(*midi.begin());\n      }\n      else if(maxi.size() != k){\n        maxi.insert(*midi.rbegin()), sum -= midi.rbegin()->first;\n        midi.erase(*midi.rbegin());\n      }\n  \n      if(num >= mini.rbegin()->first && num <= maxi.begin()->first) midi.insert({num, id}), sum += num;    //insert new\n      else if(num < mini.rbegin()->first){\n        sum += mini.rbegin()->first;\n        midi.insert(*mini.rbegin());\n        mini.erase(*mini.rbegin());\n        mini.insert({num, id});\n      }else {\n        sum += maxi.begin()->first;\n        midi.insert(*maxi.begin());\n        maxi.erase(*maxi.begin());\n        maxi.insert({num, id});\n      } \n    }\n    else if(q.size() == m){\n      vector<pair<int,int>>v(m);\n      \n      for(int i = 0; i != m; i++){\n        q.push(v[i] = q.front()); q.pop();\n      }\n      \n      sort(v.begin(), v.end());\n      int i = 0;\n      while(i != k) mini.insert(v[i++]);\n      for(int l = k + n; i != l; i++) midi.insert(v[i]), sum += v[i].first;\n      while(i != m) maxi.insert(v[i++]);\n    }\n  }\n    \n  int calculateMKAverage() {\n    return q.size() == m ? sum / n : -1;      \n  }\n};\n```
['C', 'C++']