fork(7) download
copy 
  1. //satyaki3794
  2. #include <bits/stdc++.h>
  3. #define ff first
  4. #define ss second
  5. #define pb push_back
  6. #define MOD (1000000007LL)
  7. #define LEFT(n) (2*(n))
  8. #define RIGHT(n) (2*(n)+1)
  9.  
  10. using namespace std;
  11. typedef long long ll;
  12. typedef unsigned long long ull;
  13. typedef pair<int, int> ii;
  14. typedef pair<int, ii> iii;
  15.  
  16. ll pwr(ll base, ll p, ll mod = MOD){
  17. ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
  18. }
  19.  
  20. ll gcd(ll a, ll b){
  21.     if(b == 0)  return a;
  22.     return gcd(b, a%b);
  23. }
  24.  
  25.  
  26. int n, right_low[200005];
  27. ll DP[200005], arr[200005];
  28.  
  29.  
  30. int main(){
  31.  
  32.     ios_base::sync_with_stdio(0);
  33.  
  34.     cin>>n;
  35.     for(int i=1;i<=n;i++)
  36.         cin>>arr[i];
  37.  
  38.     stack<int> st;
  39.     right_low[n] = n+1;
  40.     st.push(n);
  41.     for(int i=n-1;i>=1;i--){
  42.         while(!st.empty() && arr[st.top()] >= arr[i])
  43.             st.pop();
  44.         if(st.empty())  right_low[i] = n+1;
  45.         else    right_low[i] = st.top();
  46.         st.push(i);
  47.     }
  48.  
  49. // for(int i=1;i<=n;i++)   cout<<right_low[i]<<" ";cout<<endl;
  50.  
  51.     DP[n] = arr[n];
  52.     for(int i=n-1;i>=1;i--){
  53.         DP[i] = (right_low[i]-i)*arr[i] + DP[right_low[i]];
  54.     }
  55.  
  56.     ll ans = 0;
  57.     ans = accumulate(DP+1, DP+n+1, 0LL);
  58.     cout<<ans;
  59.     return 0;
  60. }
  61.  
Success #stdin #stdout 0s 7372KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wYc2kR
language:
C++14 (gcc 8.3)
created:
8 years 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!