[C++] Modular Code With 3 Maps  | O(Log(N)) Time
\n/* \n    Time: addElement: O(logm) | calculateMKAverage: O(1)\n    Space: O(m)\n    Tag: TreeMap, Sorting, Queue\n    Difficulty: H\n*/\n\nclass MKAverage {\n
```\n/* \n    Time: addElement: O(logm) | calculateMKAverage: O(1)\n    Space: O(m)\n    Tag: TreeMap, Sorting, Queue\n    Difficulty: H\n*/\n\nclass MKAverage {\n    map<int, int> left, middle, right;\n    queue<int> q;\n    int sizeofLeft, sizeofMiddle, sizeofRight;\n    int k;\n    long long mkSum;\n    int m;\n\n    void addToSet1(int num) {\n        left[num]++;\n        sizeofLeft++;\n    }\n\n    void deleteFromSet1(int num) {\n        left[num]--;\n        if (left[num] == 0) left.erase(num);\n        sizeofLeft--;\n    }\n\n    void addToSet2(int num) {\n        middle[num]++;\n        sizeofMiddle++;\n        mkSum += num;\n    }\n\n    void deleteFromSet2(int num) {\n        middle[num]--;\n        if (middle[num] == 0) middle.erase(num);\n        sizeofMiddle--;\n        mkSum -= num;\n    }\n\n    void addToSet3(int num) {\n        right[num]++;\n        sizeofRight++;\n    }\n\n    void deleteFromSet3(int num) {\n        right[num]--;\n        if (right[num] == 0) right.erase(num);\n        sizeofRight--;\n    }\n\npublic:\n    MKAverage(int m, int k) {\n        sizeofLeft = 0, sizeofMiddle = 0, sizeofRight = 0;\n        mkSum = 0;\n        this->k = k;\n        this->m = m;\n    }\n\n    void addElement(int num) {\n        if (sizeofLeft < k) {\n            addToSet1(num);\n            q.push(num);\n        } else if (sizeofMiddle < (m - (2 * k))) {\n            int lastEle = prev(left.end())->first;\n            if (num >= lastEle) {\n                addToSet2(num);\n            } else {\n                deleteFromSet1(lastEle);\n                addToSet1(num);\n                addToSet2(lastEle);\n            }\n            q.push(num);\n        } else if (sizeofRight < k) {\n            int last1 = prev(left.end())->first;\n            int last2 = prev(middle.end())->first;\n            if (num >= last1 && num >= last2) {\n                addToSet3(num);\n            } else if (num >= last1 && num < last2) {\n                deleteFromSet2(last2);\n                addToSet2(num);\n                addToSet3(last2);\n            } else {\n                deleteFromSet2(last2);\n                addToSet3(last2);\n                deleteFromSet1(last1);\n                addToSet2(last1);\n                addToSet1(num);\n            }\n            q.push(num);\n        } else {\n            int toErase = q.front();\n            q.pop();\n            int first3 = right.begin()->first;\n            int first2 = middle.begin()->first;\n            int first1 = left.begin()->first;\n\n            if (toErase >= first3) {\n                deleteFromSet3(toErase);\n            } else if (toErase >= first2) {\n                deleteFromSet3(first3);\n                deleteFromSet2(toErase);\n                addToSet2(first3);\n            } else {\n                deleteFromSet3(first3);\n                deleteFromSet2(first2);\n                deleteFromSet1(toErase);\n                addToSet1(first2);\n                addToSet2(first3);\n            }\n            addElement(num);\n        }\n    }\n\n    int calculateMKAverage() {\n        if (q.size() < m) return -1;\n        return mkSum / (m - (2 * k));\n    }\n};\n```
['Tree', 'Queue', 'C', 'Sorting', 'C++']