fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int> NGE(vector<int>v){
  5.     vector<int>nge(v.size());
  6.     stack<int>s;
  7. 	for(int i=0;i<v.size();i++){
  8. 	    while(!s.empty() && v[i]>v[s.top()]){
  9. 	        nge[s.top()]=i;
  10. 	        s.pop();
  11. 	    }
  12. 	    s.push(i);
  13. 	}
  14. 	while(!s.empty()){
  15. 	    nge[s.top()]=-1;
  16. 	    s.pop();
  17. 	}
  18. 	return nge;
  19. }
  20. vector<int> PGE(vector<int>v){
  21.     vector<int>pge(v.size());
  22.     stack<int>st;
  23.     for(int i=v.size()-1;i>=0;i--){
  24.         while(!st.empty() && v[i]>v[st.top()]){
  25.             pge[st.top()]=i;
  26.             st.pop();
  27.         }
  28.         st.push(i);
  29.     }
  30.     while(!st.empty()){
  31.         pge[st.top()]=-1;
  32.         st.pop();
  33.     }
  34.     return pge;
  35. }
  36.  
  37. int main() {
  38. 	// your code goes here
  39. 	int t;
  40. 	cin>>t;
  41. 	while(t--){
  42. 	    int n;
  43. 	    cin>>n;
  44. 	    vector<int>v(n);
  45. 	    for(int i=0;i<n;i++){
  46. 	        cin>>v[i];
  47. 	    }
  48. 	    int sum=0;
  49. 	    vector<int> nge=NGE(v);
  50. 	    vector<int> pge=PGE(v);
  51. 	    for(int i=0;i<n;i++){
  52. 	        int id1=pge[i]==-1?0:pge[i]+1;
  53. 	        int id2=nge[i]==-1?n-1:nge[i]-1;
  54. 	        sum+=(abs(id1-i)+1)*(abs(i-id2)+1)*v[i];
  55. 	    }
  56. 	    cout<<sum<<endl;
  57. 	}
  58. }
  59.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
2
4
5 4 8 7
6
4 5 2 25 7 8
stdout
copy 
69
349
https://ideone.com/mKNI1Z
language:
C++14 (gcc 8.3)
created:
33 days ago
visibility:
secret

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!