fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6. #define Foreach(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
  7. #define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
  8. #define rof(i,a,b) for(int (i)=(a);(i) > (b); --(i))
  9. #define rep(i, c) for(auto &(i) : (c))
  10. #define x first
  11. #define y second
  12. #define pb push_back
  13. #define PB pop_back()
  14. #define iOS ios_base::sync_with_stdio(false)
  15. #define sqr(a) (((a) * (a)))
  16. #define all(a) a.begin() , a.end()
  17. #define error(x) cerr << #x << " = " << (x) <<endl
  18. #define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
  19. #define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
  20. #define coud(a,b) cout<<fixed << setprecision((b)) << (a)
  21. #define L(x) ((x)<<1)
  22. #define R(x) (((x)<<1)+1)
  23. #define umap unordered_map
  24. #define double long double
  25. typedef long long ll;
  26. typedef pair<int,int>pii;
  27. typedef vector<int> vi;
  28. typedef complex<double> point;
  29. template <typename T> using os =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  30. template <class T>  inline void smax(T &x,T y){ x = max((x), (y));}
  31. template <class T>  inline void smin(T &x,T y){ x = min((x), (y));}
  32. const int maxn = 1e6 + 100;
  33. int a[maxn], n, l[maxn], r[maxn], ans[maxn];
  34. stack<int> s;
  35. int main(){
  36. 	scanf("%d", &n);
  37. 	For(i,0,n)
  38. 		scanf("%d", a + i);
  39. 	fill(l, l + maxn, -1);
  40. 	fill(r, r + maxn, n);
  41. 	For(i,0,n){
  42. 		while(!s.empty() && a[s.top()] >= a[i])
  43. 			s.pop();
  44. 		if(!s.empty())
  45. 			l[i] = s.top();
  46. 		s.push(i);
  47. 	}
  48. 	while(!s.empty())
  49. 		s.pop();
  50. 	rof(i,n-1,-1){
  51. 		while(!s.empty() && a[s.top()] >= a[i])
  52. 			s.pop();
  53. 		if(!s.empty())
  54. 			r[i] = s.top();
  55. 		s.push(i);
  56. 	}
  57. 	For(i,0,n){
  58. 		int len = r[i] - l[i] - 1;
  59. 		smax(ans[len], a[i]);
  60. 	}
  61. 	rof(i,n,-1)
  62. 		smax(ans[i], ans[i+1]);
  63. 	For(i,1,n+1)
  64. 		printf("%d ", ans[i]);
  65. 	cout << endl;
  66. 	return 0;
  67. }
  68.  
Success #stdin #stdout 0.01s 12860KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/FI5Vvw
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
6 days 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!