295

class MedianFinder {
public:
    multiset<int> data;
    multiset<int>::iterator mid;
    /** initialize your data structure here. */
    MedianFinder() {
        mid = data.end();
    }

    void addNum(int num) {
        int n = data.size();
        data.insert(num);
        if(!n){
            mid = data.begin();
        }
        else if(num < *mid){
            if(n%2 == 0) mid = prev(mid);
        }
        else{
            if(n&1) mid = next(mid);
        }
    }

    double findMedian() {
        int n = data.size();
        if(n&1)
            return double(*mid);
        else
            return double(*mid+*prev(mid))/2.0;
    }
};

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