Submission #71513444

---

Source Code Expand

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

int main() {
    int N;
    cin >> N;
    vector<int> P(N);
    for (int i = 0; i < N; i++) {
        cin >> P[i];
        P[i]--;
    }

    vector<int> pos(N);
    for (int i = 0; i < N; i++) {
        pos[P[i]] = i;
    }
    vector<int> parent(N);
    iota(parent.begin(), parent.end(), 0); 
    function<int(int)> find = [&](int x) -> int {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    };

    auto unite = [&](int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            parent[y] = x;
        }
    };

    vector<ll> dp(N, 0);
    for (int h = 0; h < N; h++) {
        int u = pos[h]; 
        ll left_dp = 0, right_dp = 0;
        int left_root = -1, right_root = -1;
        if (u > 0 && P[u-1] < h) {
            left_root = find(u-1);
            left_dp = dp[left_root] + abs(u - left_root);
        }
        if (u < N-1 && P[u+1] < h) {
            right_root = find(u+1);
            right_dp = dp[right_root] + abs(u - right_root);
        }
        dp[u] = max(left_dp, right_dp);
        if (left_root != -1) {
            unite(u, left_root);
        }
        if (right_root != -1) {
            unite(u, right_root);
        }
    }
    int start = pos[N-1];
    cout << dp[start];
    return 0;
}

Submission Info

Judge Result