Submission #1679996

---

Source Code Expand

#include <bits/stdc++.h>
#define F first
#define int long long
#define S second
#define pb push_back
#define Init ios::sync_with_stdio(0);

const int MX = 1000*1000+100,inf = 0x7FFFFFFF,mod=1e9+7;
using namespace std;
int n;
int inp[MX];
stack<int>stk;
struct inx{
    int r, l;
}pos[MX];
int32_t main(){
    Init
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>inp[i];
    }
    for(int i=0;i<n;i++){
        while(!stk.empty() && inp[stk.top()]>=inp[i]){
            stk.pop();
        }
        if(stk.empty()){
            pos[i].l = 0;
        }else{
            pos[i].l = stk.top()+1;
        }
        stk.push(i);
    }
    while(!stk.empty()){
        stk.pop();
    }
    for(int i=n-1;i>=0;i--){
        while(!stk.empty() && inp[stk.top()]>=inp[i]){
            stk.pop();
        }
        if(stk.empty()){
            pos[i].r = n;
        }else{
            pos[i].r = stk.top();
        }
        stk.push(i);
    }
    int sum=0;
    for(int i=0;i<n;i++){
        int dis[2] = {(i+1)-pos[i].l, pos[i].r-(i)};
        int x =((dis[0]*dis[1]));
        sum+=(x*inp[i]);
        //cout<<i<<' '<<pos[i].r<<' '<<pos[i].l<<' '<<abs(pos[i].r-pos[i].l)*inp[i]<<endl;
    }
    cout<<sum<<endl;
}

Submission Info

Judge Result