CSES/SlidingWindowMedian.cpp at main · Tirthankarpal/CSES · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include "bits/stdc++.h"
// #include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    multiset<int> a;
    multiset<int> b;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
        for(int s=0;s<k;s++){
            b.insert(arr[s]);
        }
        for(int s=0;s<(int)ceil((double)k/2);s++){
            auto it=b.begin();
            a.insert(*it);
            b.erase(it);
        }
        int i=0;
        int j=k;
        cout<<*a.rbegin()<<" ";
        while(j<n){
            if(arr[j]<=*a.rbegin()){
                if(a.find(arr[i])!=a.end()){
                    a.erase(a.find(arr[i]));
                    a.insert(arr[j]);
                }
                else{
                    b.erase(b.find(arr[i]));
                    a.insert(arr[j]);
                    b.insert(*a.rbegin());
                    a.erase(a.find(*a.rbegin()));
                }
            }
            else{
                if(a.find(arr[i])!=a.end()){
                    a.erase(a.find(arr[i]));
                    b.insert(arr[j]);
                    auto it=b.begin();
                    a.insert(*it);
                    b.erase(it);
                }
                else{
                    b.erase(b.find(arr[i]));
                    b.insert(arr[j]);
                }
            }
            i++;
            j++;
            cout<<*a.rbegin()<<" ";
        }
}