fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5.  
  6. // ---------- Monotonic Deque -----------
  7.  
  8. int main() {
  9.     ios_base::sync_with_stdio(false);
  10.     cin.tie(NULL);
  11.  
  12.     ll n, k; cin >> n >> k;
  13.     vector<ll> num(n);
  14.     for(auto &x: num ) cin >> x;
  15.  
  16.     deque<int> dq;
  17.     vector<int> ans;
  18.  
  19.     for(int i = 0; i < num.size(); i++){
  20.  
  21.         if(!dq.empty() && dq.front() == i - k){
  22.             dq.pop_front();
  23.         }
  24.  
  25.         while (!dq.empty() && num[dq.back()] < num[i])
  26.         {
  27.             dq.pop_back();
  28.         }
  29.  
  30.         dq.push_back(i);
  31.  
  32.         if ( i >= k -1){
  33.             ans.push_back(num[dq.front()]);
  34.         }
  35.  
  36.     }
  37.  
  38.     for(auto x: ans) cout << x << " ";
  39.  
  40.  
  41.  
  42.     return 0;
  43. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
8 3
1 3 -1 -3 5 3 6 7
stdout
copy 
3 3 5 5 6 7
https://ideone.com/WvZGod
language:
C++ (gcc 8.3)
created:
1 day 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!