cses.cpp

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 10;
int v[maxn];
multiset<int> cc;
multiset<int>::iterator median;

void insert(int x) {
    if (cc.empty()) {
        median = cc.insert(x);
        return;
    }
    auto v = *median;    
    cc.insert(x);
    if (x >= v) {
        if (cc.size()%2 == 1)
            median++;
    }else {
        if (cc.size()%2 == 0)
            median--;
    }
}

void erase(int x) {
    auto v = *median;
    auto it = median;
    if (x > v) {
        if (cc.size()%2 == 1)
            median--;
    }else {
        if (cc.size()%2 == 0)
            median++;
    }
    if (x == v && cc.size()%2 == 1) median--; 
    if (x != v) it = cc.find(x);
    cc.erase(it);
}

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> v[i];
    for (int i = 1; i <= k; i++)
        insert(v[i]);

    cout << *median << " ";
    for (int i = 2; i <= n - k + 1; i++) {
        erase(v[i-1]);
        insert(v[i+k-1]);
        cout << *median << " ";
    }
    cout << "\n";
    return 0;
}