solution.h

/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif

typedef pair<int, int> pii;
class MedianFinder {
   public:
    set<pii> S;
    set<pii>::iterator it1, it2;
    int time;
    MedianFinder() {
        time = 0;
    }
    void addNum(int num) {
        S.insert({num, time++});
        if (S.size() == 1) {
            it1 = S.begin();
            it2 = S.begin();
        } else {
            if (S.size() % 2 == 1) {
                auto left = *it1, right = *it2;
                if (num < left.first) {
                    it2--;
                } else if (num >= right.first) {
                    it1++;
                } else {
                    it1++;
                    it2--;
                }
            } else {
                int v = (*it1).first;
                if (num < v) {
                    it1--;
                } else if (num >= v) {
                    it2++;
                } 
            }
        }

        debug(S, *it1, *it2);

    }

    double findMedian() {
        debug("find");
        return 1.0 * (it1->first + it2->first) / 2.0;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */