提出 #71513651

---

ソースコード 拡げる

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::vector<ValueMatrix> ValueCube;
typedef std::string string;
typedef std::vector<string> StringVector;
typedef std::vector<bool> bitset;
typedef std::vector<bitset> BitMatrix;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;
typedef std::vector<PairVector> PairMatrix;
typedef std::tuple<valueType, valueType, valueType> ValueTuple;
typedef std::vector<ValueTuple> TupleVector;
typedef std::vector<TupleVector> TupleMatrix;
typedef std::set<valueType> ValueSet;
typedef std::stack<valueType> ValueStack;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N;

    std::cin >> N;

    ValueVector P(N + 1);

    for (valueType i = 1; i <= N; ++i)
        std::cin >> P[i];

    ValueVector LeftSon(N + 1, 0), RightSon(N + 1, 0);

    // 建立笛卡尔书 利用单调栈
    ValueVector stack(N + 1, 0);

    for (valueType i = 1, top = 0; i <= N; ++i) {
        valueType k = top;

        while (k > 0 && P[stack[k]] < P[i])
            --k;

        if (k > 0)
            RightSon[stack[k]] = i;

        if (k < top)
            LeftSon[i] = stack[k + 1];

        stack[++k] = i;
        top = k;
    }

    PairMatrix Tree(N + 1);

    for (valueType i = 1; i <= N; ++i) {
        if (LeftSon[i])
            Tree[i].emplace_back(LeftSon[i], std::abs(i - LeftSon[i]));

        if (RightSon[i])
            Tree[i].emplace_back(RightSon[i], std::abs(i - RightSon[i]));
    }

    auto Dfs = [&](auto &self, valueType const x) -> valueType {
        valueType ans = 0;

        for (auto const &[v, w] : Tree[x])
            ans = std::max(ans, self(self, v) + w);

        return ans;
    };

    valueType root = 1;

    for (valueType i = 1; i <= N; ++i) {
        if (P[i] > P[root])
            root = i;
    }

    std::cout << Dfs(Dfs, root) << std::endl;

    return 0;
}

提出情報

ジャッジ結果