tuki2501

Sliding Median

Sep 19th, 2020
902
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // ----------- define --------------
  5. #define int long long
  6. #define vi vector<int>
  7. #define ii pair<int,int>
  8. #define fi first
  9. #define sc second
  10. #define stoi stoll
  11. #define popcnt __builtin_popcount
  12. #define getbit(x, k) ((x >> k) & 1)
  13. #define all(x) (x).begin(),(x).end()
  14. // ---------------------------------
  15.  
  16. void Main() {
  17.   int n, k;
  18.   cin >> n >> k;
  19.   vector<int> a(n);
  20.   for (auto &i : a) {
  21.     cin >> i;
  22.   }
  23.   multiset<int> s;
  24.   for (int i = 0; i < k; i++) {
  25.     s.insert(a[i]);
  26.   }
  27.   auto it = next(s.begin(), (k + 1) / 2 - 1);
  28.   cout << *it << ' ';
  29.   for (int i = k; i < n; i++) {
  30.     if (k == 1) {
  31.       cout << a[i] << ' ';
  32.       continue;
  33.     }
  34.     if (k % 2 == 1) {
  35.       if (a[i - k] > *it || s.find(a[i - k]) == it) {
  36.         it = prev(it);
  37.       }
  38.     }
  39.     if (k % 2 == 0) {
  40.       if (a[i - k] < *it || s.find(a[i - k]) == it) {
  41.         it = next(it);
  42.       }
  43.     }
  44.     s.erase(s.find(a[i - k]));
  45.     s.insert(a[i]);
  46.     if (k % 2 == 1) {
  47.       if (a[i] >= *it) {
  48.         it = next(it);
  49.       }
  50.     }
  51.     if (k % 2 == 0) {
  52.       if (a[i] < *it) {
  53.         it = prev(it);
  54.       }
  55.     }
  56.     cout << *it << ' ';
  57.   }
  58.   cout << '\n';
  59. }
  60.  
  61. signed main() {
  62.   // freopen("in" , "r", stdin );
  63.   // freopen("out", "w", stdout);
  64.   ios::sync_with_stdio(0); cin.tie(0);
  65.   int T = 1;
  66.   // cin >> T;
  67.   while (T--) Main();
  68. }
RAW Paste Data