mickypinata

TAChi-T006: Window Sizing Puzzle

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