Submission #5230528

---

Source Code Expand

#include <bits/stdc++.h>

#define For(i, l, r) for (register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Rep(i, r) for (register int i = (0), i##end = (int)(r); i < i##end; ++i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl

using namespace std;

typedef long long ll;

template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }

inline int read() {
	int x(0), sgn(1); char ch(getchar());
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
	for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
	return x * sgn;
}

void File() {
#ifdef zjp_shadow
	freopen ("F.in", "r", stdin);
	freopen ("F.out", "w", stdout);
#endif
}

const int N = 200100;

const ll inf = 0x3f3f3f3f3f3f3f3f;

#define mid ((l + r) >> 1)
#define lson o << 1, l, mid
#define rson o << 1 | 1, mid + 1, r

template<int Maxn>
struct Segment_Tree {

	ll minv[Maxn], tag[Maxn];

	inline void add(int o, ll uv) {
		minv[o] += uv; tag[o] += uv;
	}

	inline void push_down(int o) {
		if (tag[o]) 
			add(o << 1, tag[o]), add(o << 1 | 1, tag[o]), tag[o] = 0;
	}

	inline void push_up(int o) {
		minv[o] = min(minv[o << 1], minv[o << 1 | 1]);
	}

	void Update(int o, int l, int r, int up, ll uv) {
		if (l == r) { minv[o] = uv; return; } push_down(o);
		up <= mid ? Update(lson, up, uv) : Update(rson, up, uv); push_up(o);
	}

	void Update(int o, int l, int r, int ul, int ur, ll uv) {
		if (ul <= l && r <= ur) { add(o, uv); return; } push_down(o);
		if (ul <= mid) Update(lson, ul, ur, uv);
		if (ur > mid) Update(rson, ul, ur, uv); push_up(o);
	}

	ll Query(int o, int l, int r, int ql, int qr) {
		if (ql <= l && r <= qr) return minv[o];
		push_down(o);
		if (qr <= mid) return Query(lson, ql, qr);
		if (ql > mid) return Query(rson, ql, qr);
		return min(Query(lson, ql, qr), Query(rson, ql, qr));
	}

};

Segment_Tree<N << 2> TL, TR;

#define root 1, 1, n

int n, q, x[N]; ll f[N], g[N], ans = inf;

inline void Modify(int pos, ll uv) {
	TL.Update(root, pos, uv - pos); TR.Update(root, pos, uv + pos);
}

int main () {

	File();

	n = read(); q = read(); 
	x[0] = read(); int p = read();
	For (i, 1, n) Modify(i, abs(p - i));

	For (i, 1, q) {
		x[i] = read();
		ll tmp = min(TL.Query(root, 1, x[i]) + x[i], TR.Query(root, x[i], n) - x[i]);
		TL.Update(root, 1, n, abs(x[i - 1] - x[i])); 
		TR.Update(root, 1, n, abs(x[i - 1] - x[i])); Modify(x[i - 1], tmp);
	}

	ll ans = inf;
	For (i, 1, n)
		chkmin(ans, TL.Query(root, i, i) + i);
	printf ("%lld\n", ans);

	return 0;

}

Submission Info

Judge Result