Submission #7399111


Source Code Expand

Copy
#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

Submission Time
Task E - Second Sum
User nu50218
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2674 Byte
Status TLE
Exec Time 2111 ms
Memory 34688 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 3
AC × 16
TLE × 6
Set Name Test Cases
Sample 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt
All 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 01-small-01.txt, 01-small-02.txt, 01-small-03.txt, 01-small-04.txt, 01-small-05.txt, 02-large-01.txt, 02-large-02.txt, 02-large-03.txt, 02-large-04.txt, 02-large-05.txt, 03-max-01.txt, 03-max-02.txt, 04-min-01.txt, 05-sorted-01.txt, 05-sorted-02.txt, 06-almost-sorted-01.txt, 06-almost-sorted-02.txt, 06-almost-sorted-03.txt, 06-almost-sorted-04.txt
Case Name Status Exec Time Memory
00-sample-01.txt AC 1 ms 256 KB
00-sample-02.txt AC 1 ms 256 KB
00-sample-03.txt AC 1 ms 256 KB
01-small-01.txt AC 1 ms 256 KB
01-small-02.txt AC 1 ms 256 KB
01-small-03.txt AC 1 ms 256 KB
01-small-04.txt AC 1 ms 256 KB
01-small-05.txt AC 1 ms 256 KB
02-large-01.txt AC 68 ms 30592 KB
02-large-02.txt AC 42 ms 19328 KB
02-large-03.txt AC 72 ms 31872 KB
02-large-04.txt AC 72 ms 32384 KB
02-large-05.txt AC 44 ms 20352 KB
03-max-01.txt AC 78 ms 34688 KB
03-max-02.txt AC 78 ms 34688 KB
04-min-01.txt AC 1 ms 256 KB
05-sorted-01.txt TLE 2105 ms 33280 KB
05-sorted-02.txt TLE 2105 ms 33920 KB
06-almost-sorted-01.txt TLE 2105 ms 32000 KB
06-almost-sorted-02.txt TLE 2111 ms 31488 KB
06-almost-sorted-03.txt TLE 2105 ms 33152 KB
06-almost-sorted-04.txt TLE 2105 ms 31360 KB