Submission #1476079

---

Source Code Expand

#include<cstdio>
#include<cstring>
#include<algorithm>
#define lc (o << 1)
#define rc (o << 1 | 1)
#define mid ((l+r) >> 1)
#define int long long
using namespace std;

inline int read(){
	char ch = getchar(); int x = 0;
	while (ch < '0' || '9' < ch) ch = getchar();
	while ('0' <= ch && ch <= '9') { x = x*10 + ch-'0'; ch = getchar(); }
	return x;
}
const int maxn = 200009;
int L[maxn<<2], R[maxn<<2], lazyL[maxn<<2], lazyR[maxn<<2], x[maxn];
int n, Q, A, B, cost, ans = 1e18;

void build(int T[], int op, int o, int l, int r){
	if (l == r) { T[o] = abs(l-B) + op*l; return; }
	build(T, op, lc, l, mid); build(T, op, rc, mid+1, r);
	T[o] = min(T[lc], T[rc]);
}

void pushdown(int T[], int lazy[], int o){
	T[lc] += lazy[o]; lazy[lc] += lazy[o];
	T[rc] += lazy[o]; lazy[rc] += lazy[o];
	lazy[o] = 0;
}

void update(int T[], int lazy[], int o, int l, int r, int x, int y){
	if (l == r) { T[o] = min(T[o], y); return; }
	pushdown(T, lazy, o);
	if (x <= mid) update(T, lazy, lc, l, mid, x, y);
	else update(T, lazy, rc, mid+1, r, x, y);
	T[o] = min(T[lc], T[rc]);
}

int query(int T[], int lazy[], int o, int l, int r, int x, int y){
	if (l == x && y == r) return T[o];
	pushdown(T, lazy, o); int res = 1e18;
	if (x <= mid) res = min(res, query(T, lazy, lc, l, mid, x, min(mid, y)));
	if (mid+1 <= y) res = min(res, query(T, lazy, rc, mid+1, r, max(mid+1, x), y));
	return res;
}

signed main(){
	n = read(); Q = read();
	x[0] = A = read(); B = read();
	for (int i=1; i<=Q; i++) x[i] = read();
	build(L, -1, 1, 1, n); build(R, 1, 1, 1, n);
	for (int i=1; i<=Q; i++){
		cost = min(query(L, lazyL, 1, 1, n, 1, x[i]) + x[i],
				   query(R, lazyR, 1, 1, n, x[i], n) - x[i]);
		L[1] += abs(x[i]-x[i-1]); lazyL[1] += abs(x[i]-x[i-1]);
		R[1] += abs(x[i]-x[i-1]); lazyR[1] += abs(x[i]-x[i-1]);
		update(L, lazyL, 1, 1, n, x[i-1], cost-x[i-1]);
		update(R, lazyR, 1, 1, n, x[i-1], cost+x[i-1]);
	}
	for (int i=1; i<=n; i++)
		ans = min(ans, query(L, lazyL, 1, 1, n, i, i) + i);
	printf("%lld", ans);
	return 0;
}

Submission Info

Judge Result