480

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        multiset<int> window(nums.begin(), nums.begin()+k);
        auto mid = next(window.begin(), k/2);
        vector<double> ans;

        for(int i=k; i<=nums.size(); i++){
            double median = 0.0;
            if(k&1)
                median = *mid;
            else
                median = (double(*mid) + *prev(mid, 1))/2.0;
            ans.push_back(median);

            if(i == nums.size()) break;

            window.insert(nums[i]);
            if(nums[i] < *mid)
                mid--;
            if(nums[i-k] <= *mid)
                mid++;
            window.erase(window.lower_bound(nums[i-k]));
        }
        return ans;
    }
};