Submission #71492305

---

Source Code Expand

/* Code By WCM */
/*
Date:
大致思路：
复杂度：
期望得分：
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <vector>
#include <queue>
#include <map>
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define int long long

using namespace std;

inline int read();
void write(int);
void writeln(int);

const int N = 2e5 + 5;
int n, p[N], pos[N], G[N][2], du[N], fa[N], mx[N], f[N];
bool vis[N];
int getfa(int x) { return fa[x] == x ? x : fa[x] = getfa(fa[x]); }
void uni(int u, int v) {
	int fu = getfa(u), fv = getfa(v);
	if(fu == fv) return ;
	fa[fv] = fu, mx[fu] = max(mx[fu], mx[fv]);
}
int getmx(int x) { return mx[getfa(x)]; }
int Abs(int x) { return x < 0 ? -x : x; }

signed main() {

//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);

	n = read();
	for(int i = 1; i <= n; i++) p[i] = read(), pos[p[i]] = i;
	for(int i = 1; i <= n - 1; i++) {
		int u = p[i], v = p[i + 1];
		G[u][du[u]++] = v, G[v][du[v]++] = u;
	}
	for(int i = 1; i <= n; i++) fa[i] = mx[i] = i;
	for(int h = 1; h <= n; h++) {
		if(h > 1) {
			vis[h - 1] = 1;
			for(int j = 0; j < du[h - 1]; j++) if(vis[G[h - 1][j]]) uni(h - 1, G[h - 1][j]);
		}
		int res = 0;
		for(int j = 0; j < du[h]; j++) {
			int ni = G[h][j];
			if(ni < h) {
				int hh = getmx(ni);
				res = max(res, Abs(pos[h] - pos[hh]) + f[hh]);
			}
		}
		f[h] = res;
	}
	printf("%lld\n", f[n]);
	
//	printf("\nThe time used: ");
//	printf("%.2lfs",(double)clock()/CLOCKS_PER_SEC);

	return 0;

}

inline int read() {
	int res = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
	while(ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = getchar();
	return res * f;
}

void write(int x) {
	static int sta[35];
	int top = 0;
	do { sta[top++] = x % 10, x /= 10; } while(x);
	while(top) putchar(sta[--top] ^ 48);
}

void writeln(int x) {
	write(x);
	putchar('\n');
}

Submission Info

Judge Result