Advertisement
erek1e

SPOJ - ARRAYSUB

Jul 23rd, 2022
871
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.57 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <deque>
  4.  
  5. using namespace std;
  6.  
  7. int main() {
  8.     int n; cin >> n;
  9.     vector<int> a(n);
  10.     for (int &x : a) cin >> x;
  11.     int k; cin >> k;
  12.     deque<int> candidates;
  13.     for (int i = 0; i < n; ++i) {
  14.         while (!candidates.empty() && a[candidates.back()] <= a[i]) candidates.pop_back();
  15.         candidates.push_back(i);
  16.         if (!candidates.empty() && candidates.front()+k == i) candidates.pop_front();
  17.         if (i >= k-1) cout << a[candidates.front()] << ' ';
  18.     }
  19.     cout << endl;
  20.     return 0;
  21. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement