Josif_tepe

Untitled

Mar 22nd, 2026
366
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.27 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. #include <cstring>
  5. using namespace std;
  6. typedef long long ll;
  7. const int maxn = 1e6 + 5;
  8. const int INF = 2e9;
  9. int segment_tree[3 * maxn];
  10. int a[maxn];
  11. int n;
  12.  
  13. int merge_nodes(int A, int B) {
  14.     return max(A, B);
  15. }
  16. void build_tree(int L, int R, int node) {
  17.     if(L == R) {
  18.         segment_tree[node] = a[L];
  19.     }
  20.     else {
  21.         int middle = (L + R) / 2;
  22.         build_tree(L, middle, 2 * node);
  23.         build_tree(middle + 1, R, 2 * node + 1);
  24.         segment_tree[node] = merge_nodes(segment_tree[2 * node], segment_tree[2 * node + 1]);
  25.     }
  26. }
  27.  
  28. // L R i L R j L R
  29. int query(int i, int j, int L = 0, int R = n - 1, int node = 1) {
  30.     if(i <= L and R <= j) {
  31.         return segment_tree[node];
  32.     }
  33.     if(R < i or j < L) {
  34.         return -INF;
  35.     }
  36.     int middle = (L + R) / 2;
  37.     return merge_nodes(query(i, j, L, middle, 2 * node), query(i, j, middle + 1, R, 2 * node + 1));
  38. }
  39. int main()
  40. {
  41.     ios_base::sync_with_stdio(false);
  42.     int k;
  43.    
  44.     cin >> n;
  45.     cin >> k;
  46.     for(int i = 0; i < n; i++) {
  47.         cin >> a[i];
  48.     }
  49.    
  50.     build_tree(0, n - 1, 1);
  51.    
  52.     for(int i = 0; i < n - k + 1; i++) {
  53.         cout << query(i, i + k - 1) << " ";
  54.     }
  55.     return 0;
  56. }
  57.  
Advertisement
Add Comment
Please, Sign In to add comment