提出 #7401267


ソースコード 拡げる

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]]);
    }
};

ll left(const ll N, const ll& i, const ll& border, const vector<ll>& P, SparseTable& st) {
    if (i <= 0) return -1;
    if (st.query_max(0, i - 1) <= border) return -1;
    ll imax = i;
    ll imin = 0;
    while (imax - imin > 1) {
        ll imid = (imax + imin) / 2;
        if (st.query_max(imid, i - 1) > border) {
            imin = imid;
        } else {
            imax = imid;
        }
    }
    return imin;
}

ll right(const ll N, const ll& i, const ll& border, const vector<ll>& P, SparseTable& st) {
    if (N - 1 <= i) return N;
    if (st.query_max(i + 1, N - 1) <= border) return N;
    ll imax = N;
    ll imin = i;
    while (imax - imin > 1) {
        ll imid = (imax + imin) / 2;
        if (st.query_max(i + 1, imid) > border) {
            imax = imid;
        } else {
            imin = imid;
        }
    }
    return imax;
}

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 = left(N, i, P[i], P, st);
        ll left2 = left(N, left1, P[i], P, st);
        ll right1 = right(N, i, P[i], P, st);
        ll right2 = right(N, right1, P[i], P, st);
        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;
}

提出情報

提出日時
問題 E - Second Sum
ユーザ nu50218
言語 C++14 (GCC 5.4.1)
得点 500
コード長 3338 Byte
結果 AC
実行時間 238 ms
メモリ 34688 KB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 500 / 500
結果
AC × 3
AC × 22
セット名 テストケース
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
ケース名 結果 実行時間 メモリ
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 192 ms 30592 KB
02-large-02.txt AC 113 ms 19328 KB
02-large-03.txt AC 198 ms 31872 KB
02-large-04.txt AC 211 ms 32384 KB
02-large-05.txt AC 117 ms 20352 KB
03-max-01.txt AC 228 ms 34688 KB
03-max-02.txt AC 238 ms 34688 KB
04-min-01.txt AC 1 ms 256 KB
05-sorted-01.txt AC 126 ms 33280 KB
05-sorted-02.txt AC 139 ms 33920 KB
06-almost-sorted-01.txt AC 117 ms 32000 KB
06-almost-sorted-02.txt AC 123 ms 31488 KB
06-almost-sorted-03.txt AC 124 ms 33152 KB
06-almost-sorted-04.txt AC 120 ms 31360 KB