Sliding Window Median

1#include<bits/stdc++.h>
2using namespace std;
3#define int long long
4signed main(){
5  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
6  int n,k; cin>>n>>k;
7  multiset<int> lf,rg;
8  int a[n]; for(int i=0,res=0;i<n;++i){
9    cin>>a[i];
10    if(lf.size() && *lf.rbegin()<a[i]) rg.emplace(a[i]);
11    else lf.emplace(a[i]);
12    while(rg.size()>lf.size()) lf.emplace(*rg.begin()),rg.erase(rg.begin());
13    while(lf.size()-rg.size()>1) rg.emplace(*lf.rbegin()),lf.erase(lf.find(*lf.rbegin()));
14    if(i>=k){
15      if(lf.size() && *lf.rbegin()<a[i-k]) rg.erase(rg.find(a[i-k]));
16      else lf.erase(lf.find(a[i-k]));
17      while(rg.size()>lf.size()) lf.emplace(*rg.begin()),rg.erase(rg.begin());
18      while(lf.size()-rg.size()>1) rg.emplace(*lf.rbegin()),lf.erase(lf.find(*lf.rbegin()));
19    }
20    if(i>=k-1) cout<<*lf.rbegin()<<" ";
21  }
22  cout<<'\n';
23  return 0;
24}