Submission #1255256

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)




typedef long long ll;
#define INF 1LL<<40
#define def INF
template<class V, int NV> struct SegTree {
    V comp(V l, V r) { return min(l, r); };
    vector<V> val; SegTree() { val = vector<V>(NV * 2, def); }
    V get(int l, int r) { //[l,r]
        if (l > r) return def;
        l += NV; r += NV + 1; V ret = def;
        while (l < r) { if (l & 1) ret = comp(ret, val[l++]); if (r & 1) ret = comp(ret, val[--r]); l /= 2; r /= 2; }
        return ret;
    }
    void update(int i, V v) { i += NV; val[i] = v; while (i>1) i >>= 1, val[i] = comp(val[i * 2], val[i * 2 + 1]); }
    void add(int i, V v) { update(i, val[i + NV] + v); }
};
int N, Q, A, B, X[201010];
//-----------------------------------------------------------------------------------
/*ll dp[201010][201010][201010];
ll orderN3() {
    rep(i, 0, Q + 1) rep(a, 0, N + 1) rep(b, 0, N + 1) dp[i][a][b] = INF;
    dp[0][0][0] = 0;
    rep(i, 0, Q) rep(a, 0, N + 1) rep(b, 0, N + 1) if (dp[i][a][b] != INF) {
        dp[i + 1][X[i]][b] = min(dp[i + 1][X[i]][b], dp[i][a][b] + abs(a - X[i]));
        dp[i + 1][a][X[i]] = min(dp[i + 1][a][X[i]], dp[i][a][b] + abs(b - X[i]));
    }

    ll ans = INF;
    rep(a, 0, N + 1) rep(b, 0, N + 1) ans = min(ans, dp[Q][a][b]);
    return ans;
}*/
//-----------------------------------------------------------------------------------
/*ll dp2[2][201010];
ll orderN2() {
    rep(i, 0, N + 1) dp2[0][i] = INF;
    dp2[0][A] = 0;

    rep(i, 0, Q) {
        int b;
        if (i == 0) b = B;
        else b = X[i - 1];

        // reset
        rep(a, 0, N + 1) dp2[(i + 1) % 2][a] = INF;

        // 1. b -> X[i]
        rep(a, 0, N + 1) dp2[(i + 1) % 2][a] = min(dp2[(i + 1) % 2][a], dp2[i % 2][a] + abs(b - X[i]));
        // 2. a -> X[i]
        rep(a, 0, N + 1) dp2[(i + 1) % 2][b] = min(dp2[(i + 1) % 2][b], dp2[i % 2][a] + abs(a - X[i]));
    }

    ll ans = INF;
    rep(a, 0, N + 1) ans = min(ans, dp2[Q % 2][a]);
    return ans;
}*/
//-----------------------------------------------------------------------------------
SegTree<ll, 1 << 18> dp3, dpplus, dpminus;
ll offset = 0;
ll orderNlogN() {
    dp3.update(A, 0);
    dpplus.update(A, 0+A);
    dpminus.update(A, 0-A);

    rep(i, 0, Q) {
        int b;
        if (i == 0) b = B;
        else b = X[i - 1];

        // 1. b -> X[i]
        offset += abs(X[i] - b);

        // 2. a -> X[i]
        ll mi = INF;
        mi = min(mi, dpminus.get(0, X[i]) + X[i]);
        mi = min(mi, dpplus.get(X[i], N) - X[i]);
        mi -= abs(X[i] - b);

        dp3.update(b, mi);
        dpplus.update(b, mi + b);
        dpminus.update(b, mi - b);
    }

    ll ans = dp3.get(0, N) + offset;
    return ans;
}
//-----------------------------------------------------------------------------------
int main() {
    cin >> N >> Q >> A >> B;
    rep(i, 0, Q) scanf("%d", &X[i]);

    cout << orderNlogN() << endl;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:95:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     rep(i, 0, Q) scanf("%d", &X[i]);
                                    ^

Judge Result