fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1e6 + 5;
  5. int n, a[N], l1[N], r1[N], l2[N], r2[N];
  6. stack<int> s;
  7.  
  8. int main() 
  9. {
  10. 	cin.tie(0)->ios_base::sync_with_stdio(0);
  11.     cin >> n;
  12.     for (int i = 0; i < n; ++i) cin >> a[i];
  13.     for (int i = 0; i < n; ++i) 
  14.     {
  15.         while (!s.empty() && a[s.top()] < a[i]) s.pop();
  16.         l1[i] = s.empty() ? -1 : s.top();
  17.         s.push(i);
  18.     }
  19.     while (!s.empty()) s.pop();
  20.     for (int i = n - 1; i >= 0; --i) 
  21.     {
  22.         while (!s.empty() && a[s.top()] <= a[i]) s.pop();
  23.         r1[i] = s.empty() ? n : s.top();
  24.         s.push(i);
  25.     }
  26.  
  27.     while (!s.empty()) s.pop();
  28.     for (int i = 0; i < n; ++i) 
  29.     {
  30.         while (!s.empty() && a[s.top()] > a[i]) s.pop();
  31.         l2[i] = s.empty() ? -1 : s.top();
  32.         s.push(i);
  33.     }
  34.     while (!s.empty()) s.pop();
  35.     for (int i = n - 1; i >= 0; --i) 
  36.     {
  37.         while (!s.empty() && a[s.top()] >= a[i]) s.pop();
  38.         r2[i] = s.empty() ? n : s.top();
  39.         s.push(i);
  40.     }
  41.  
  42.     long long z = 0;
  43.     for (int i = 0; i < n; ++i) 
  44.     {
  45.         long long mx = 1LL * (i - l1[i]) * (r1[i] - i);
  46.         long long mn = 1LL * (i - l2[i]) * (r2[i] - i);
  47.         z += a[i] * (mx - mn);
  48.     }
  49.  
  50.     cout << z;
  51. }
  52.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Nd7N43
language:
C++ (gcc 8.3)
created:
145 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!