Submission #1212437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212437		qilby	Cat Exercise (JOI23_ho_t4)	C++20	41 / 100	35 ms	8644 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 200009;

ll n, h[N], w[N], f[N], lft[N], rgt[N];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> h[i];
        w[h[i]] = i;
    }

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
    }

    vector < int > v;

    for (int i = 1; i <= n; i++) {
        while (!v.empty() && h[v.back()] <= h[i]) v.pop_back();
        if (v.empty()) lft[i] = 0; else lft[i] = v.back();
        v.push_back(i);
    }

    v.clear();

    for (int i = n; i >= 1; i--) {
        while (!v.empty() && h[v.back()] <= h[i]) v.pop_back();
        if (v.empty()) rgt[i] = n + 1; else rgt[i] = v.back();
        v.push_back(i);
    }

    for (int x = 1; x <= n; x++) {
        f[lft[w[x]]] = max(f[lft[w[x]]], f[w[x]] + abs(lft[w[x]] - w[x]));
        f[rgt[w[x]]] = max(f[rgt[w[x]]], f[w[x]] + abs(rgt[w[x]] - w[x]));
    }

    cout << *max_element(f + 1, f + n + 1);
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 10
• Subtask 5: 20 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26