Submission #7399111

---

Source Code Expand

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

struct SparseTable {
    vector<vector<long long>> table_min;
    vector<vector<long long>> table_max;
    vector<long long> log_table;
    SparseTable(const vector<long long> &A) : table_min(), table_max() {
        log_table.resize(A.size() + 1);
        log_table[1] = 0;
        for (long long i = 2; i <= A.size(); i++) {
            log_table[i] = log_table[i / 2] + 1;
        }
        table_min.resize(A.size());
        fill(table_min.begin(), table_min.end(), vector<long long>(log_table[A.size()] + 1));
        for (long long i = 0; i < A.size(); i++) table_min[i][0] = A[i];
        for (long long i = 1; (1 << i) <= A.size(); i++) {
            for (long long j = 0; j + (1 << i) <= A.size(); j++) {
                table_min[j][i] = min(table_min[j][i - 1], table_min[j + (1 << (i - 1))][i - 1]);
            }
        }
        table_max.resize(A.size());
        fill(table_max.begin(), table_max.end(), vector<long long>(log_table[A.size()] + 1));
        for (long long i = 0; i < A.size(); i++) table_max[i][0] = A[i];
        for (long long i = 1; (1 << i) <= A.size(); i++) {
            for (long long j = 0; j + (1 << i) <= A.size(); j++) {
                table_max[j][i] = max(table_max[j][i - 1], table_max[j + (1 << (i - 1))][i - 1]);
            }
        }
    }
    long long query_min(long long i, long long j) {
        return min(table_min[i][log_table[j - i + 1]], table_min[j - (1 << log_table[j - i + 1]) + 1][log_table[j - i + 1]]);
    }
    long long query_max(long long i, long long j) {
        return max(table_max[i][log_table[j - i + 1]], table_max[j - (1 << log_table[j - i + 1]) + 1][log_table[j - i + 1]]);
    }
};

int main() {
    int N;
    cin >> N;
    vector<ll> P(N);
    for(size_t i = 0;i < N;i++){
        cin >> P[i];
    }
    SparseTable st(P);
    ll ans = 0;
    for(int i = 0;i < N;i++){
        ll left1 = -1,left2 = -1,right1 = -1,right2 = -1;
        int j = i-1;
        while(0 <= j && P[i] > P[j])j--;
        left1 = j;
        j--;
        while(0 <= j && P[i] > P[j])j--;
        left2 = j;
        j = i+1;
        while(j < N && P[i] > P[j])j++;
        right1 = j;
        j++;
        while(j < N && P[i] > P[j])j++;
        right2 = j;
        // cerr << i << ':' << left2 << ' ' << left1 << ' ' << right1 << ' ' << right2 << endl;
        if(i+1 < N)if(st.query_max(i+1,N-1) > P[i])ans += (right2 - right1) * (i - left1) * P[i];
        if(0 <= i-1)if(st.query_max(0,i-1) > P[i])ans += (right1 - i) * (left1 - left2) * P[i];
    }
    cout << ans << endl;
}

Submission Info

Judge Result