CSES – Sliding Median

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
//declare
int n,k;
vector<int> v;
multiset<int> L,R;
//
signed main(){
    fastio;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        int x; cin>>x;
        v.push_back(x);
    }
    for(int i=0;i<k;i++){
        if(L.empty()) R.insert(v[i]);
        else if(R.empty()) L.insert(v[i]);
        else{
            if(*L.rbegin() >= v[i]) L.insert(v[i]);
            else R.insert(v[i]);
        }
        if(L.size() > R.size()+1) R.insert(*L.rbegin()), L.erase(prev(L.end()));
        if(R.size() > L.size()+1) L.insert(*R.begin()), R.erase(R.begin());
    }
    cout<<((L.size() >= R.size()) ? *L.rbegin() : *R.begin())<<" ";
    int lp = 0, rp = k;
    while(rp < n){
        if(L.size() && *L.rbegin() >= v[lp]) L.erase(L.find(v[lp++]));
        else R.erase(R.find(v[lp++]));
 
        if(L.size() > R.size()+1) R.insert(*L.rbegin()), L.erase(prev(L.end()));
        if(R.size() > L.size()+1) L.insert(*R.begin()), R.erase(R.begin());
  
        if(L.empty()) R.insert(v[rp++]);
        else if(R.empty()) L.insert(v[rp++]);
        else{
            if(*L.rbegin() >= v[rp]) L.insert(v[rp++]);
            else R.insert(v[rp++]);
        }
        
        if(L.size() > R.size()+1) R.insert(*L.rbegin()), L.erase(prev(L.end()));
        if(R.size() > L.size()+1) L.insert(*R.begin()), R.erase(R.begin());
 
        cout<<((L.size() >= R.size()) ? *L.rbegin() : *R.begin())<<" ";
    }
    cout<<"\n";
    return 0;
}