fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define sc(x) scanf("%d",&x);
  4. #define pr(x) printf("%d \n",x);
  5. #define scll(x) scanf("%lld",&x);
  6. #define scll2(x,y) scanf("lld",&x,&y);
  7. #define prll(x) printf("%lld \n",x);
  8. #define sc2(x,y) scanf("d",&x,&y);
  9. #define ll long long
  10. #define PB push_back
  11. #define MP make_pair
  12. #define PII  pair<int,int>
  13. using namespace std;
  14.  
  15. int n,l,r;
  16. ll a[100000+10],x,mod=1e9 + 7;
  17. int R[100000+10],L[100000+10];
  18. ll ans;
  19. stack<int> s;
  20.  
  21. int main(){
  22.     // move the declaration inside as it cant be handled by the stack,
  23.     scanf("%d",&n);
  24.     for(int i=0;i<n;i++){
  25.         scanf("%lld",&a[i]);
  26.         // remove the mod statement to prevent changing the value beforehand
  27.         a[i] += i+1;
  28.     }
  29.  
  30.     L[0]=0;
  31.     s.push(0);
  32.     for(int i=1;i<n;i++){
  33.         while(!s.empty() && a[i] > a[s.top()]){
  34.             //add a -1 in i-s.top()
  35.             R[s.top()] = i-1-s.top();
  36.             s.pop();
  37.         }
  38.         //add a -1 in i-s.top()
  39.         L[i] = (s.empty())? i : i-s.top()-1;
  40.         s.push(i);
  41.     }
  42.     while(!s.empty()){
  43.         //add a -1 in n-s.top()
  44.         R[s.top()] = n-s.top()-1;
  45.         s.pop();
  46.     }
  47.     //after changing the L & R arrays,
  48.     //L[i] & R[i] represent length of sub-array with elements,
  49.     //smaller than a[i] to the left and right respectively
  50.     ans=0;
  51.     for(int i=0;i<n;i++){
  52.         //now x will represent the range in which a[i] is maximum
  53.         x = (L[i] + R[i] + 1)%mod;
  54.         x = (x * a[i]); 
  55.         ans = (ans + x)%mod;
  56.     }
  57.     cout<<ans<<endl;
  58. }
  59.  
Success #stdin #stdout 0s 4980KB
comments ()
stdin
copy 
3
1 2 3
stdout
copy 
28
https://ideone.com/buHMAg
language:
C++14 (gcc 8.3)
created:
9 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!