日経 F Flights

https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_f

The orange course is shorter than the black one.

The orange course is shorter than the black one.

Therefore, points on the orange area are unnecessary after this move.

Points on the orange area are unnecessary after this move.

Thus, an optimal move is like this.

Zissoh ga mendoh. Nanika hohshin wo matigaetaka.

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

#define Z (1 << 17)

const long long INF = 1e18;

long long S[Z * 2];
long long L[Z * 2];
bool MARK[Z * 2];

long long min(long long x, long long y) {
    return x < y ? x : y;
}

void to(long long *x, long long y) {
    if (*x > y) *x = y;
}

void apply(int k, long long v) {
    if (!MARK[k]) return;
    to(&S[k], v);
    to(&L[k], v);
}

void push(int k) {
    if (L[k] >= INF) return;
    apply(k << 1 | 0, L[k]);
    apply(k << 1 | 1, L[k]);
    L[k] = INF;
}

void pull(int k) {
    S[k] = min(S[k << 1], S[k << 1 | 1]);
}

void update(int l, int r, long long v) {
    l += Z;
    r += Z - 1;
    for (int i = 17; i >= 1; i--) push(l >> i), push(r >> i);
    for (int i = l, j = r; i <= j; i >>= 1, j >>= 1) {
        if ((i & 1) == 1) apply(i++, v);
        if ((j & 1) == 0) apply(j--, v);
    }
    for (int i = 17; i >= 1; i--) push(l >> i), push(r >> i);
    for (int i = 1; i <= 17; i++) pull(l >> i), pull(r >> i);
}

long long query(int l, int r) {
    l += Z;
    r += Z - 1;
    for (int i = 17; i >= 1; i--) push(l >> i), push(r >> i);
    long long ans = INF;
    for (int i = l, j = r; i <= j; i >>= 1, j >>= 1) {
        if ((i & 1) == 1) to(&ans, S[i++]);
        if ((j & 1) == 0) to(&ans, S[j--]);
    }
    return ans;
}

int N, M;
int X[100000], Y[100000], C[100000];
int U[100000];
int V[100000];
int W[100000];

int ind(int y) {
    int k = N;
    for (int i = 1 << 16; i >= 1; i >>= 1) if (k - i >= 0) {
        if (Y[V[k - i]] > y) k -= i;
    }
    return k;
}

int main(void) {
    int s, t;
    scanf("%d %d %d", &N, &s, &t);
    s--; t--;
    for (int i = 0; i < N; i++) {
        scanf("%d %d %d", &X[i], &Y[i], &C[i]);
        U[i] = i;
        V[i] = i;
    }
    if (Y[s] < Y[t]) {
        swap(s, t);
    }
    sort(U, U + N, [&](int i, int j) { return X[i] != X[j] ? X[i] < X[j] : Y[i] < Y[j]; });
    sort(V, V + N, [&](int i, int j) { return Y[i] < Y[j]; });
    for (int i = 0; i < N; i++) {
        W[V[i]] = i;
    }
    for (int i = 0; i < Z * 2; i++) {
        S[i] = INF;
        L[i] = INF;
    }
    for (int i_ = 0; i_ < N; i_++) {
        int i = U[i_];
        int j = ind(Y[i]);
        long long v = query(0, j) + C[i];
        if (i == s) {
            v = 0;
        }
        int k = W[i] + Z;
        for (int i = 17; i >= 1; i--) push(k >> i);
        for (int i = 0; i <= 17; i++) {
            MARK[k >> i] = true;
            to(&S[k >> i], v);
        }
        update(0, j, v + C[i]);
    }
    for (int i = 1; i < Z; i++) push(i);
    printf("%lld\n", S[W[t] + Z]);
    return 0;
}