Josif_tepe

Untitled

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