Salvens

C

Aug 14th, 2023
956
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.08 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <array>
  4. #include <vector>
  5. #include <numeric>
  6. #include <random>
  7. #include <chrono>
  8. #include <set>
  9. #include <map>
  10. #include <queue>
  11.  
  12. #define int long long
  13. using namespace std;
  14.  
  15. const long long INF = 1e9 + 7;
  16. const int MAXN = 15e4 + 10;
  17. const int N = 1e5 + 10;
  18.  
  19. array<int, MAXN> sq, a;
  20. const int B = 666;
  21.  
  22. inline void build(int n) {
  23.     sq.fill(INF);
  24.     for (int i = 0; i < n; ++i) {
  25.         sq[i / B] = min(sq[i / B], a[i]);
  26.     }
  27. }
  28.  
  29. inline int get(int l, int r) {
  30.     int ans = INF;
  31.     while (l <= r) {
  32.         if (l % B == 0 && l + B - 1 <= r) {
  33.             ans = min(ans, sq[l / B]);
  34.             l += B;
  35.         } else {
  36.             ans = min(ans, a[l]);
  37.             ++l;
  38.         }
  39.     }
  40.     return ans;
  41. }
  42.  
  43. signed main() {
  44.     ios_base::sync_with_stdio(false);
  45.     cin.tie(nullptr);
  46.  
  47.     int n, k;
  48.     cin >> n >> k;
  49.     for (int i = 0; i < n; ++i) {
  50.         cin >> a[i];
  51.     }
  52.     build(n);
  53.     int l = 0, r = k - 1;
  54.     while (r < n) {
  55.         cout << get(l, r) << ' ';
  56.         ++l, ++r;
  57.     }
  58. }
  59.  
Advertisement
Add Comment
Please, Sign In to add comment