Submission #1793425

---

Source Code Expand

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

using ll = long long;

template <typename T> T inf;
template <> constexpr int inf<int> = 1e9;
template <> constexpr ll inf<ll> = 1e18;

int main() {
    int N;
    cin >> N;
    vector<int> pos(N + 1);
    for(int i = 0; i < N; ++i) {
        int a; cin >> a;
        pos[a] = i;
    }

    ll res = 0;
    set<int> used_pos;
    for(int i = 1; i <= N; ++i) {
        ll l2, r2;
        auto r = used_pos.lower_bound(pos[i]);
        if(r == end(used_pos)) {
            r2 = N;
        } else {
            r2 = *r;
        }
        if(r == begin(used_pos)) {
            l2 = -1;
        } else {
            l2 = *prev(r);
        }
        ll c = (pos[i] - l2) * (r2 - pos[i]);
        //cout << l2 << ' ' << pos[i] << ' ' << r2 << " -> " << c << endl;
        res += 1LL * c * i;
        used_pos.insert(pos[i]);
    }
    cout << res << endl;
}

Submission Info

Judge Result