Submission #904960

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(void) {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> L(n), R(n);
    for (int i = 0; i < n; ++ i) {
        L[i] = R[i] = i;
        cin >> a[i];
    }


    vector<int> st;
    for (int i = 0; i < n; ++ i) {
        while (!st.empty() && a[i] < a[st.back()]) {
            L[i] = L[st.back()];
            st.pop_back();
        }
        st.push_back(i);
    }

    st.clear();
    for (int i = n - 1; i >= 0; -- i) {
        while (!st.empty() && a[i] < a[st.back()]) {
            R[i] = R[st.back()];
            st.pop_back();
        }
        st.push_back(i);
    }

    ll ans = 0;
    for (int i = 0; i < n; ++ i) {
        //cerr << L[i] << ' ' << R[i] << endl;
        ans += (ll)a[i] * (R[i] - i + 1) * (i - L[i] + 1);
    }

    cout << ans << endl;

    return 0;
}

Submission Info

Judge Result