Submission #1814892

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 200005;

long long n, a[NMAX], L[NMAX], R[NMAX], st[NMAX];

int main(){
    //freopen("input.txt","r", stdin);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    int top = 0;
    st[0] = 0;
    for(int i = 1; i <= n; i++){
        while(top > 0 && a[st[top]] >= a[i]) top--;
        L[i] = st[top] + 1;
        st[++top] = i;
    }

    top = 0, st[0] = n+1;
    for(int i = n; i >= 1; i--){
        while(top > 0 && a[st[top]] >= a[i]) top--;
        R[i] = st[top] - 1;
        st[++top] = i;
    }

    long long res = 0, t1, t2;
    for(int i = 1; i <= n; i++){
        t1 = i-L[i];
        t2 = R[i] - i;
        res += (t1 + t2 + 1 +t1*t2)*a[i];
    }
    cout << res;
}

Submission Info

Judge Result