Submission #1184835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184835		anmattroi	Train (APIO24_train)	C++17	5 / 100	115 ms	14740 KiB

train

#include "train.h"
#include <bits/stdc++.h>
#define maxn 100005
#define fi first
#define se second
#define int64_t long long
using namespace std;
using ii = pair<int, int>;
using il = pair<int, int64_t>;
using li = pair<int64_t, int>;

int n, m, w, t[maxn];
int leftEnds[maxn], rightEnds[maxn];
int64_t st[4*maxn];
int e[maxn];

struct edge {int x, y, a, b, c;} edges[maxn];
ii meals[maxn];

int64_t kc[maxn], nho[maxn];
int start[maxn], stop[maxn];

void upd(int u, int64_t d, int r = 1, int lo = 1, int hi = m) {
    if (lo == hi) {
        st[r] = d;
        return;
    }
    int mid = (lo + hi) >> 1;
    if (u <= mid) upd(u, d, r<<1, lo, mid);
    else upd(u, d, r<<1|1, mid+1, hi);
    st[r] = min(st[r<<1], st[r<<1|1]);
}

int64_t get(int u, int v, int r = 1, int lo = 1, int hi = m) {
    if (u <= lo && hi <= v) return st[r];
    int mid = (lo + hi) >> 1;
    return min(u <= mid ? get(u, v, r<<1, lo, mid) : LLONG_MAX/2,
               v > mid ? get(u, v, r<<1|1, mid+1, hi) : LLONG_MAX/2);
}


int64_t mainProgram() {
    sort(meals + 1, meals + w + 1);
    for (int i = 1; i <= w; i++) {
        leftEnds[i] = meals[i].fi;
        rightEnds[i]= meals[i].se;
    }
    sort(edges + 1, edges + m + 1, [&](const edge &u, const edge &v) {
        if (u.y != v.y) return u.y < v.y;
        if (u.b != v.b) return u.b < v.b;
        return u.x < v.x;
         });
    for (int i = 1; i <= m; i++) {
        auto [x, y, a, b, c] = edges[i];

        if (!start[y]) start[y] = i;
        stop[y] = i;

        nho[i]  = c;
        nho[i] += 1LL * (lower_bound(rightEnds + 1, rightEnds + w + 1, a) - rightEnds - 1) * t[x];
        nho[i] -= 1LL * (upper_bound(rightEnds + 1, rightEnds + w + 1, b) - rightEnds - 1) * t[y];
    }

    for (int i = 1; i <= 4*m; i++) st[i] = LLONG_MAX/2;

    iota(e + 1, e + m + 1, 1);
    sort(e + 1, e + m + 1, [&](int x, int y) {
        if (edges[x].b != edges[y].b) return edges[x].b < edges[y].b;
        return edges[x].a < edges[y].a;
         });

    for (int i = 1; i <= m; i++) kc[i] = LLONG_MAX/2;

    for (int o = 1; o <= m; o++) {
        int i = e[o];
        auto [x, y, a, b, c] = edges[i];
        int ST = start[x], EN = stop[x];

        if (ST!=0) {
            int L = ST, R;
            if (1) {
                int lo = ST-1, hi = EN+1;
                while (hi - lo > 1) {
                    int mid = (lo + hi) >> 1;
                    if (edges[mid].b <= a) lo = mid;
                    else hi = mid;
                }
                R = lo;
            }
            if (L <= R) kc[i] = min(LLONG_MAX/2, get(L, R) + nho[i]);
        }
        if (edges[i].x == 1)
            kc[i] = min(kc[i], nho[i]);
        upd(i, kc[i]);
    }

    int64_t ans = LLONG_MAX/2;
    for (int i = 1; i <= m; i++)
    if (edges[i].y == n)
        ans = min(ans, kc[i]);

    ans += 1LL * t[n] * w;
    return (ans >= LLONG_MAX/10 ? -1 : ans);
}

long long solve(int N, int M, int W, vector<int> T,
                vector<int> X, vector<int> Y, vector<int> A, vector<int> B, vector<int> C,
                vector<int> L, vector<int> R) {
    n = N; m = M; w = W;
    for (int i = 1; i <= n; i++) t[i] = T[i-1];
    for (int i = 1; i <= m; i++) edges[i] = edge{X[i-1]+1, Y[i-1]+1, A[i-1], B[i-1], C[i-1]};
    for (int i = 1; i <= w; i++) meals[i] = ii{L[i-1], R[i-1]};

	return mainProgram();
}

/*
3 3 1
20 30 40
0 1 1 15 10
1 2 20 30 5
0 2 18 40 40
16 19

40
*/
/*
3 5 6
30 38 33
0 2 12 16 38
1 0 48 50 6
0 1 26 28 23
0 2 6 7 94
1 2 49 54 50
32 36
14 14
42 45
37 40
2 5
4 5

197
*/

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60