sliding_window_median.cpp (1064B)
1 #include <bits/stdc++.h> 2 #include <ext/pb_ds/tree_policy.hpp> 3 #include <ext/pb_ds/assoc_container.hpp> 4 5 using namespace std; 6 namespace __gnu_pbds{ 7 template<class T> 8 using ordered_multiset = tree<T, 9 null_type, 10 less_equal<T>, 11 rb_tree_tag, 12 tree_order_statistics_node_update>; 13 } 14 using namespace __gnu_pbds; 15 16 17 using ui = unsigned int; 18 using ul = unsigned long; 19 using ll = long long; 20 using ull = unsigned long long; 21 22 using vi = vector<int>; 23 using vui = vector<ui>; 24 using vl = vector<long>; 25 using vul = vector<ul>; 26 using vll = vector<ll>; 27 using vull = vector<ull>; 28 29 void solve() 30 { 31 int n, k; 32 cin >> n >> k; 33 ordered_multiset<int> s; 34 queue<int> q; 35 for (int i = 0; i < n; i++) { 36 int x; 37 cin >> x; 38 s.insert(x); 39 q.push(x); 40 if (i >= k - 1) { 41 cout << *(s.find_by_order((k-1)/2)) << " "; 42 int p = q.front(); 43 s.erase(s.find_by_order(s.order_of_key(p))); 44 q.pop(); 45 } 46 } 47 cout << "\n"; 48 } 49 50 int main() 51 { 52 ios::sync_with_stdio(0); 53 cin.tie(0); 54 solve(); 55 }