CSES – Sliding Cost

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
//declare
int n,k,Lsum,Rsum;
vector<int> v;
multiset<int> L,R;
//
void update(){
    if(L.size() == R.size() - 2){
        L.insert(*R.begin());
        Lsum += *R.begin(), Rsum -= *R.begin();
        R.erase(R.begin());
    }
    if(R.size() == L.size() - 2){
        R.insert(*L.rbegin());
        Rsum += *L.rbegin(), Lsum -= *L.rbegin();
        L.erase(prev(L.end()));
    }
}
void insert(int x){
    if(L.empty()) R.insert(x), Rsum += x;
    else if(R.empty()) L.insert(x), Lsum += x;
    else if(x <= *L.rbegin()) L.insert(x), Lsum += x;
    else R.insert(x), Rsum += x;
    update();
}
void remove(int x){
    if(L.empty()) R.erase(R.find(x)), Rsum -= x;
    else if(R.empty()) L.erase(L.find(x)), Lsum -= x;
    else if(x <= *L.rbegin()) L.erase(L.find(x)), Lsum -= x;
    else R.erase(R.find(x)), Rsum -= x;
    update();
}
int cost(){
    int median, ans = 1e18;
    if(L.empty()){
        median = *R.begin();
        return (median * L.size() - Lsum) + (Rsum - median * R.size());
    }
    if(R.empty()){
        median = *L.rbegin();
        return (median * L.size() - Lsum) + (Rsum - median * R.size());
    }
    median = *R.begin();
    ans = min(ans, (int)((median * L.size() - Lsum) + (Rsum - median * R.size())));
    median = *L.rbegin();
    ans = min(ans, (int)((median * L.size() - Lsum) + (Rsum - median * R.size())));
    return ans;
}
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++){
        insert(v[i]);
    }
    cout<<cost()<<" ";
    for(int i=k;i<n;i++){
        remove(v[i-k]);
        insert(v[i]);
        cout<<cost()<<" ";
    }
    cout<<"\n";
    return 0;
}