fork download
copy 
  1. #include<iostream>
  2. #include<set>
  3. #include<vector>
  4. #define SZ(X) ((int)(X).size())
  5. using namespace std;
  6. const int SIZE = 1 << 20;
  7. int main() {
  8.     int n, k;
  9.     cin >> n >> k;
  10.     vector<int> x(n);
  11.     multiset<int> small, big; // big 維護前 k / 2 + 1 大的數，small 維護剩下的數
  12.     int need = k / 2 + 1;
  13.     for(int i = 0; i < n; i++) {
  14.         cin >> x[i];
  15.         big.insert(x[i]);
  16.         if(big.size() > need) {
  17.             small.insert(*big.begin());
  18.             big.erase(big.begin());
  19.         }
  20.         if(i >= k) {
  21.             if(small.find(x[i - k]) != small.end()) {
  22.                 small.erase(small.find(x[i - k]));
  23.             } else {
  24.                 big.erase(big.find(x[i - k]));
  25.                 big.insert(*prev(small.end()));
  26.                 small.erase(prev(small.end()));
  27.             }
  28.         }
  29.         if(i >= k - 1) cout << *big.begin() << (i + 1 < n ? ' ' : '\n');
  30.     }
  31. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
8 3
2 4 3 5 8 1 2 1
stdout
copy 
3 4 5 5 2 1
https://ideone.com/Oh0WnW
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!