YEZAELP

SMMR-Chi-006: Window Sizing Puzzle

Dec 5th, 2021
934
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int N = 1e6 + 10;
  5. int ar[N], mx[N];
  6.  
  7. int main(){
  8.  
  9.     int n;
  10.     scanf("%d", &n);
  11.  
  12.     for(int i=1;i<=n;i++)
  13.         scanf("%d", &ar[i]);
  14.     ar[n + 1] = 0;
  15.  
  16.     stack <int> st;
  17.     for(int i=1;i<=n+1;i++){
  18.         while(!st.empty() and ar[st.top()] > ar[i]){
  19.             int idx = st.top(); st.pop();
  20.             int len = 0;
  21.             if(st.empty()) len = i - 1;
  22.             else len = i - st.top() - 1;
  23.             mx[len] = max(mx[len], ar[idx]);
  24.         }
  25.         st.push(i);
  26.     }
  27.  
  28.     for(int i=n;i>=1;i--)
  29.         mx[i] = max(mx[i], mx[i + 1]);
  30.  
  31.     for(int i=1;i<=n;i++)
  32.         printf("%d ", mx[i]);
  33.  
  34.     return 0;
  35. }
RAW Paste Data