fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h> 
  3.  
  4. using namespace std;
  5.  
  6. int main() {
  7. 	int n;
  8. 	cin>>n;
  9. 	vector<int> arr(n);
  10. 	for(int i=0;i<n;i++){
  11. 		cin>>arr[i];
  12. 	}
  13.  
  14. 	vector<int> prefix(n,0);
  15. 	vector<int> suffix(n,0);
  16.  
  17. 	// Count descending steps leading into index i+1
  18. 	for(int i=0;i<n-1;i++){
  19. 		if(arr[i+1]<arr[i]){
  20. 			if(i==0){
  21. 				prefix[i]=1;
  22. 			}
  23. 			else{
  24. 				prefix[i]=prefix[i-1]+1;
  25. 			}
  26. 		}
  27. 		else{
  28. 			prefix[i]=0;
  29. 		}
  30. 	}
  31.  
  32. 	// Count ascending steps extending forward from index i
  33. 	for(int i=n-2;i>=0;i--){
  34. 		if(arr[i]<arr[i+1]){
  35. 			suffix[i]=suffix[i+1]+1;
  36. 		}
  37. 		else{
  38. 			suffix[i]=0;
  39. 		}
  40. 	}
  41.  
  42. 	long long ans=0;
  43.  
  44. 	for(int i=1;i<n-1;i++){
  45. 		// prefix[i-1] is dec steps into i; suffix[i] is inc steps out of i
  46. 		long long k = 1LL * prefix[i-1] * suffix[i];
  47. 		ans = ans + k;
  48. 	}
  49. 	cout<<ans<<endl;
  50.  
  51. 	return 0;
  52. }
Success #stdin #stdout 0s 5340KB
comments (?)
stdin
copy 
4
5 3 4 8
stdout
copy 
2
https://ideone.com/YKtPhy
language:
C++14 (gcc 8.3)
created:
3 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!