fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. ll n,a[300005],l[300005],r[300005],kq = 0;
  5. int main()
  6. {
  7.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  8.   //  freopen("ZNANSTVENIK.inp", "r", stdin);
  9.   //  freopen("ZNANSTVENIK.out", "w", stdout);
  10.     cin >> n;
  11.     memset(l,0,sizeof(l));
  12.     memset(r,0,sizeof(r));
  13.     for(int i = 1; i <= n; i++)
  14.     {
  15.         cin >> a[i];
  16.     }
  17.     for(int i = 1; i <= n; i++)
  18.     {
  19.         l[i] = i - 1;
  20.         while(l[i] > 0 && a[l[i]] >= a[i]) l[i] = l[l[i]];
  21.     }
  22.     for(int i = n; i >= 1; i--)
  23.     {
  24.         r[i] = i + 1;
  25.         while(r[i] <= n && a[r[i]] >= a[i]) r[i] = r[r[i]];
  26.     }
  27.     for(int i = 1; i <= n; i++)
  28.        kq -= a[i]*(i - l[i])*(r[i] - i);
  29.     for(int i = 1; i <= n; i++)
  30.     {
  31.         l[i] = i - 1;
  32.         while(l[i] > 0 && a[l[i]] <= a[i]) l[i] = l[l[i]];
  33.     }
  34.     for(int i = n; i >= 1; i--)
  35.     {
  36.         r[i] = i + 1;
  37.         while(r[i] <= n && a[r[i]] <= a[i]) r[i] = r[r[i]];
  38.     }
  39.     for(int i = 1; i <= n; i++)
  40.     kq += a[i]*(i - l[i] )*(r[i] - i);
  41.     cout << kq;
  42. }
  43.  
Success #stdin #stdout 0.01s 8992KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4OIEm3
language:
C++ (gcc 8.3)
created:
4 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!