Submission #1696039

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
const long long inf = 1e18;

struct SegmentTree {
	long long t[N << 2];
	SegmentTree() { for (int i = 0; i < (N << 2); ++i) t[i] = inf; }

	#define mid ((l + r) >> 1)
	void upd(int v, int l, int r, int pos, long long val) {
		if (l > r || pos < l || pos > r) return;
		if (l == r) { t[v] = val; return; }
		upd(v << 1, l, mid, pos, val); upd(v << 1 | 1, mid + 1, r, pos, val);
		t[v] = min(t[v << 1], t[v << 1 | 1]);
	}
	long long get(int v, int l, int r, int L, int R) {
		if (l > r || R < l || L > r) return inf;
		if (L <= l && r <= R) return t[v];
		return min(get(v << 1, l, mid, L, R), get(v << 1 | 1, mid + 1, r, L, R));
	}
} L, R;

int n;
long long T, E;
long long x[N];
long long f[N];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> E >> T;
	for (int i = 1; i <= n; ++i) cin >> x[i];
	
	int ptr = 0;
	for (int i = 1; i <= n; ++i) {
		L.upd(1, 1, n, i, f[i - 1] - x[i - 1] - x[i] * 2);
		R.upd(1, 1, n, i, f[i - 1] - x[i - 1]);
		while(ptr < i && (x[i] - x[ptr + 1]) * 2 > T) ++ptr;
		f[i] = L.get(1, 1, n, 1, ptr) + 3LL * x[i];
		f[i] = min(f[i], R.get(1, 1, n, ptr + 1, i) + T + x[i]);
	}

	long long ans = f[n] + E - x[n];

	cout << ans << endl;
}

Submission Info

Judge Result