fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     // your code goes here
  6.     int t;
  7.     if (cin>>t){
  8.         while(t--){
  9.             int n;
  10.             cin>>n;
  11.             vector<int>v(n);
  12.             vector<pair<int,int>>a(n);
  13.             for(int i=0;i<n;i++){
  14.                 cin>>v[i];
  15.                 a[i]={v[i],i};
  16.             }
  17.             sort(a.begin(),a.end(),greater<pair<int,int>>());
  18.             set<int>s;
  19.             long long sum = 0;
  20.             for (int i=0;i<n;i++){
  21.                 int val=a[i].first;
  22.                 int id=a[i].second;
  23.                 auto it=s.insert(id).first;
  24.                 // prev greater and second prev greater than v[i]
  25.                 int j1 = -1, j2 = -1;
  26.                 auto l=it;
  27.                 if (l!=s.begin()){
  28.                     l--;
  29.                     j1 =*l;
  30.                     if (l!=s.begin()){
  31.                         auto ll=l;
  32.                         ll--; 
  33.                         j2=*ll;
  34.                     }
  35.                 }
  36.                 // next greater and second next greater than v[i]
  37.                 int i1 = n, i2 = n;
  38.                 auto r = it;
  39.                 r++;
  40.                 if (r!=s.end()){
  41.                     i1=*r;
  42.                     auto rr=r;
  43.                     rr++; 
  44.                     if (rr!=s.end()){
  45.                         i2=*rr;
  46.                     }
  47.                 }
  48.                 // # of subarrays where v[i] is 2nd max on right side of array
  49.                 int r_sub=0;
  50.                 if (i1!=n){
  51.                     int l_way=id-j1;
  52.                     int r_way=i2-i1;
  53.                     r_sub=l_way*r_way;
  54.                 }
  55.                 // # of subarrays where v[i] is 2nd max on left side of array
  56.                 int l_sub=0;
  57.                 if (j1!=-1){
  58.                     int l_way=j1-j2;
  59.                     int r_way=i1-id;
  60.                     l_sub=l_way*r_way;
  61.                 }
  62.                 sum+=(r_sub+l_sub)*val;
  63.             }
  64.             cout<<sum<<endl;
  65.         }
  66.     }
  67. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
3
4
5 4 8 7
6
4 5 2 25 7 8
3
2 3 0
stdout
copy 
34
89
4
https://ideone.com/d2FUbd
language:
C++14 (gcc 8.3)
created:
32 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!