Submission #1690199

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 10;
const int INF = 2e9;

int dp[MAXN], seg[4 * MAXN], x[MAXN];

void _set(int v, int l, int r, int p, int x) {
    if (r - l == 1) {
	seg[v] = x;
	return;
    }
    int mid = (r + l) / 2;
    if (p < mid) 
	_set(2 * v, l, mid, p, x);
    else
	_set(2 * v + 1, mid, r, p, x);
    seg[v] = min(seg[2 * v], seg[2 * v + 1]);
}

int query(int v, int l, int r, int s, int t) {
    if (s <= l && r <= t)
	return seg[v];
    int mid = (l + r) / 2, res = INF;
    if (s < mid)
	res = min(res, query(2 * v, l, mid, s, t));
    if (t > mid)
	res = min(res, query(2 * v + 1, mid, r, s, t));
    return res;
}

int lower(int val, int s, int t) {
    if (t - s == 1)
	return s;
    int mid = (s + t) / 2;
    if (x[mid-1] >= val)
	return lower(val, s, mid);
    else
	return lower(val, mid, t);
}

main() {
    int N, T, E;
    cin >> N >> E >> T;
    T *= 2;
    for (int i = 0; i < N; i ++) cin >> x[i], x[i] *= 2;
    for (int i = 0; i < N; i ++) {
	int last = lower(x[i] - T/2, 0, N);
	if (last <= 1) {
	    dp[i] = (last?2 * x[i] - 2 * x[0] : T);
	    if(last)dp[i] = min(dp[i], dp[last - 1] + T);
	    _set(1, 0, N, i, dp[i] - 2 * x[i+1]);
	    continue;
	}
	dp[i] = query(1, 0, N, 0, last-1) + 2 * x[i]; 
	dp[i] = min(dp[i], dp[last- 1] + T);
	dp[i] = min(dp[i], 2 * (x[i] - x[0]));
	_set(1, 0, N, i, dp[i] - 2 * x[i+1]);
    }
    cout << dp[N -1]/2 + E << endl;
}

Submission Info

Judge Result