fork(5) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxN = 1e5 + 10;
  4. int arr[maxN];
  5. int ans[maxN];
  6. vector<int> g[maxN];
  7. int n;
  8.  
  9. int main() {
  10. 	cin >> n;
  11. 	vector<int> s;
  12. 	for (int i = 1; i <= n; ++i) {
  13. 		cin >> arr[i];
  14. 		while (not s.empty() and arr[s.back()] >= arr[i]) {
  15. 			s.pop_back();
  16. 		}
  17. 		if (not s.empty()) {
  18. 			g[s.back()].push_back(i);
  19. 		}
  20. 		s.push_back(i);
  21. 	}
  22.  
  23. 	s.clear();
  24. 	for (int i = 1; i <= n; ++i) {
  25. 		for (int v : g[i]) {
  26. 			while (not s.empty() and arr[s.back()] >= arr[v]) {
  27. 				s.pop_back();
  28. 			}
  29. 			if (not s.empty()) {
  30. 				ans[v] = arr[s.back()];
  31. 			}
  32. 			s.push_back(v);
  33. 		}
  34. 		while (not s.empty() and arr[s.back()] >= arr[i]) {
  35. 			s.pop_back();
  36. 		}
  37. 		s.push_back(i);
  38. 	}
  39. 	for (int i = 1; i <= n; ++i) {
  40. 		cout << ans[i] << " ";
  41. 	} cout << endl;
  42. 	return 0;
  43. }
Success #stdin #stdout 0s 18360KB
comments (?)
stdin
copy 
8
2 4 5 3 1 7 10 8
stdout
copy 
0 0 2 0 0 3 1 1
https://ideone.com/zpJk7A
language:
C++14 (gcc 8.3)
created:
5 years 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!