Submission #71503889

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define debug(arg) cout << "[" << #arg << "]: " << arg << endl
#else
#define debug(arg) 42
#endif

using llu = uint64_t;
using ll = int64_t;

#define vec vector
#define pb push_back
#define all(n) begin(n), end(n)

struct Tree {
	int n;
	vec<int> s;
	Tree(int n, vec<int> const& p) : n(n), s(2*n) {
		copy(all(p), s.begin() + n);
		for (int i = n - 1; i; --i) s[i] = max(s[i<<1], s[i<<1|1]);
	}
	int get(int l, int r) {
		int mx = 0;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (l&1) mx = max(mx, s[l++]);
			if (r&1) mx = max(mx, s[--r]);
		}
		return mx;
	}
};

void solv() {
	int n; cin >> n;
	vec<int> p(n); for (auto &i : p) cin >> i, --i;
	vec<int> ip(n); for (int i = 0; i < n; ++i) ip[p[i]] = i;
	Tree tree(n, p);
	function<pair<int, ll>(int, int)> process = [&](int l, int r) -> pair<int, ll> {
		if (r <= l || l < 0 || r > n) return {0, -1ll};
		int mx = tree.get(l, r);
		int mxp = ip[mx];
		auto [mxlp, lc] = process(l, mxp);
		auto [mxrp, rc] = process(mxp + 1, r);
		ll ans = 0;
		if (lc != -1) ans = max(ans, lc + abs(mxp - mxlp));
		if (rc != -1) ans = max(ans, rc + abs(mxp - mxrp));
		return {mxp, ans};
	};
	cout << process(0, n).second << '\n';;
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int t = 1;
	//cin >> t;
	while (t--) solv();
	return 0;
}

Submission Info

Judge Result