fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4.  
  5. vector<long long> solve(int N, vector<int> H) {
  6. 	vector<ll> pre(N);
  7. 	pre[0] = H[0];
  8. 	for(int i=1; i<N; i++) pre[i] = pre[i-1] + H[i];
  9. 	vector<ll> ans(N,0);
  10. 	stack<int> s;
  11. 	for(int i=N-1; i>=0; i--) {
  12. 		while(!s.empty() && H[i] < H[s.top()]) {
  13. 			ans[s.top()] = pre[s.top()-1] - pre[i];
  14. 			s.pop();
  15. 		}
  16. 		s.push(i);
  17. 	}
  18. 	while(!s.empty()) {
  19. 		if(s.top() != 0) ans[s.top()] = pre[s.top()-1];
  20. 		s.pop();
  21. 	}
  22. 	return ans;
  23. }
  24.  
  25. int main() {
  26. 	// your code goes here
  27. 	int N;
  28. 	cin >> N;
  29. 	vector<int> H(N);
  30. 	for(int i=0; i<N; i++) cin >> H[i];
  31. 	vector<ll> ans = solve(N,H);
  32. 	for(int i: ans) cout << i << " ";
  33. 	return 0;
  34. }
Success #stdin #stdout 0.01s 5428KB
comments (?)
stdin
copy 
4
2 -2 3 7
stdout
copy 
0 2 0 0
https://ideone.com/Ksvi5y
language:
C++14 (gcc 8.3)
created:
2 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!