fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const long long MaxN = 1e6 + 5;
  4. long long n, a[MaxN], res=0;
  5. stack<long long> st;
  6. int main()
  7. {
  8.     freopen("file.inp", "r", stdin);
  9.     freopen("file.ans", "w", stdout);
  10.     cin >> n;
  11.     for (long long i=1; i<=n; i++)
  12.     {
  13.         cin >> a[i];
  14.         vector<long long> v;
  15.         while(!st.empty() && a[i]>a[st.top()])
  16.         {
  17.             v.push_back(a[st.top()]);
  18.             st.pop();
  19.         }
  20.         v.push_back(a[i]);
  21.         for (long long j=0; j<v.size()-1; j++)
  22.         {
  23.             res+=v[j+1]-v[j];
  24.         }
  25.         st.push(i);
  26.             a[n+1]=max(a[n+1],a[i]);
  27.     }
  28.     vector<long long > v;
  29.     while(!st.empty()&&a[n+1]>a[st.top()])
  30.     {
  31.         v.push_back(a[st.top()]);
  32.         st.pop();
  33.     }
  34.     v.push_back(a[n+1]);
  35.     for (long long i=0; i<v.size()-1; i++) res+=v[i+1]-v[i];
  36.     cout << res;
  37. }
  38.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/zkQxvU
language:
C++14 (gcc 8.3)
created:
2 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!