fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define _nhatminh  int main()
  3. #define ll long long
  4. #define str string
  5. #define fir first
  6. #define sec second
  7. #define ld long double
  8. #define pb push_back
  9. #define MOD (ll)1000000007
  10. #define freopen(name) if(fopen(name".INP","r")) {freopen (name".INP","r",stdin); freopen (name".OUT","w",stdout);}
  11. #define ALL(x) (x).begin(),(x).end()
  12. #define piint pair < int , int >
  13. #define piL pair < int , ll>
  14. #define pLL pair < ll , ll >
  15. #define TIME (1.0*clock()/CLOCKS_PER_SEC)
  16. using namespace std;
  17. const int Max_n=5*1e5;
  18. ll a[Max_n+3];
  19. // void sub1(){
  20. //     ll res = 0 ;
  21. //     ll ans = 0 ;
  22. //     for (int i = 1 ; i <= n ; i ++ )
  23. //     {
  24. //         ll res = 0 ;
  25. //         int j = i ;
  26. //         int minn = a[i] ;
  27. //         while ( (j-1) >= 1 ){
  28. //             j -- ; 
  29. //             minn = min ( res , a[j]);
  30. //             res += minn ;
  31. //         }
  32. //     }
  33. // }
  34. ll l[Max_n + 3 ];
  35. int n ; 
  36.  ll g[Max_n+3 ] , r[Max_n+3] ; 
  37. void subfull (){
  38.     stack < int > s , ret ;
  39.     for (int i = 1 ; i <= n ; i ++ ){
  40.         while (!s.empty() && a[i] <= a[s.top()]){
  41.             s.pop() ;
  42.         }
  43.         if (!s.size()){
  44.             l[i] = a[i] * i  ; 
  45.         } 
  46.         else l[i] = ( i - s.top()  )  * a[i] + l[s.top()] ;
  47.         s.push ( i ) ;
  48.     }
  49.     s = ret ; 
  50.     for (int i = n ; i >= 1 ; i -- ){
  51.         while (s.size() && a[i] <= a[s.top()]){
  52.             s.pop() ;
  53.         }
  54.         if (!s.size()) {
  55.             r[i] = 1ll*( n - i + 1) * a[i] ;
  56.         }
  57.         else r[i] = 1ll*(abs( i - s.top() )) * a[i] + r[s.top()];
  58.         s.push ( i ) ; 
  59.     }
  60.     // ll maxx = 0 ;
  61.  
  62.     for(int i = 1 ; i <= n ; i ++ ){
  63.         g[i] = ( l[i] + r[i]) - a[i] ; 
  64.         // res = max ( res , g[i] );
  65.     }
  66.     auto id = max_element( g + 1 , g + n + 1 ) - g ;
  67.     g[id] = a[id] ;
  68.     for (int i = id - 1 ; i >= 1 ; i -- ){
  69.         g[i] = min ( g[i+1] , a[i] ) ;
  70.         // cout << g[i] << ' '
  71.     } 
  72.     for (int i = id + 1 ; i <= n ; i ++ ){
  73.         g[i] = min ( g[i-1] , a[i] ) ;
  74.     } 
  75.     for (int i = 1 ; i <= n ; i ++ ){
  76.         cout << g[i] << '\n';
  77.     }
  78.     // int r =
  79. }
  80. void solve(){
  81.     // al < ai < ar
  82.     // ll res = 0 ; 
  83.     cin >> n ;
  84.     for (int i = 1 ; i <=n  ; i ++ ){
  85.         cin >> a[i] ;
  86.     }
  87.     if ( n > -1  ) subfull() ;
  88. }
  89. _nhatminh{
  90. freopen("");
  91. ios_base::sync_with_stdio(0);
  92. cin.tie(0); cout.tie(0);
  93. int q=1;
  94. // cin >> q;
  95. while (q--)
  96.     solve();
  97. cerr << '\n' << "Time elapsed " << TIME << "s.\n";
  98. return (0);
  99. }
Success #stdin #stdout #stderr 0s 5932KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Time elapsed 0.004491s.
https://ideone.com/5Nbh2a
language:
C++14 (gcc 8.3)
created:
2 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!