Submission #1202456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202456		anmattroi	Train (APIO24_train)	C++20	100 / 100	274 ms	111088 KiB

train

#ifdef EVAL
#include "train.h"
#endif

#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], root[maxn];
int A[maxn], B[maxn], n1 = 0, n2 = 0;

constexpr int64_t INF = LLONG_MAX/2;

int64_t ans = INF;

namespace pst {
    int nt = 0, it[22*maxn], L[22*maxn], R[22*maxn];

    int build(int lo = 1, int hi = n2) {
        if (lo == hi) return ++nt;
        int cur = ++nt, mid = (lo + hi) >> 1;
        L[cur] = build(lo, mid);
        R[cur] = build(mid+1, hi);
        return nt;
    }

    int upd(int u, int d, int oldver, int lo = 1, int hi = n2) {
        if (lo == hi) {
            it[++nt] = it[oldver] + d;
            return nt;
        }
        int cur = ++nt, mid = (lo + hi) >> 1;
        if (u <= mid) {
            L[cur] = upd(u, d, L[oldver], lo, mid);
            R[cur] = R[oldver];
        } else {
            L[cur] = L[oldver];
            R[cur] = upd(u, d, R[oldver], mid+1, hi);
        }
        it[cur] = it[L[cur]] + it[R[cur]];
        return cur;
    }

    int get(int u, int v, int r, int lo = 1, int hi = n2) {
        if (u <= lo && hi <= v) return it[r];
        int mid = (lo + hi) >> 1;
        return (u <= mid ? get(u, v, L[r], lo, mid) : 0)
            + (v > mid ? get(u, v, R[r], mid+1, hi) : 0);
    }
    int bfind(int k, int rootOne, int rootTwo, int lo = 1, int hi = n2) {
        if (lo == hi) return lo;
        int mid = (lo + hi) >> 1, trai = it[L[rootTwo]]-it[L[rootOne]];
        if (k > trai) return bfind(k-trai, R[rootOne], R[rootTwo], mid+1, hi);
        return bfind(k, L[rootOne], L[rootTwo], lo, mid);
    }
}

struct edge {
    int x, y, a, b, c;

    bool operator < (const edge &other) const {
        return a < other.a;
    }
} edges[maxn];

struct nnode {
    int x;
    nnode() {}
    nnode(int _x) : x(_x) {}

    bool operator < (const nnode &other) const {
        if (edges[x].b != edges[other.x].b) return edges[x].b < edges[other.x].b;
        return x < other.x;
    }
};

ii meals[maxn];
int64_t dp[maxn];
deque<int> q[maxn];
set<nnode> events[maxn];


int64_t mainProgram() {
    sort(edges + 1, edges + m + 1);
    for (int i = 1; i <= w; i++) {
        A[++n1] = meals[i].fi;
        B[++n2] = meals[i].se;
    }
    sort(A + 1, A + n1 + 1);
    sort(B + 1, B + n2 + 1);

    n1 = unique(A + 1, A + n1 + 1) - A - 1;
    n2 = unique(B + 1, B + n2 + 1) - B - 1;

    sort(meals + 1, meals + w + 1, [&](const ii &a, const ii &b) {return a.fi < b.fi;});

    root[0] = pst::build();
    for (int i = 1, it = 1; i <= n1; i++) {
        root[i] = root[i-1];
        while (it <= w && meals[it].fi == A[i]) {
            int p = lower_bound(B + 1, B + n2 + 1, meals[it].se) - B;
            root[i] = pst::upd(p, 1, root[i]);
            ++it;
        }
    }
    for (int i = 1; i <= m; i++) dp[i] = INF;

//    for (int i = 1; i <= m; i++) cerr << edges[i].x << ' ' << edges[i].y << ' ' << edges[i].a << ' ' << edges[i].b << ' ' << edges[i].c << "\n";

    for (int i = 1; i <= m; i++) {
        for (nnode ip : events[i]) {
            int idx = ip.x;
            deque<int> &cur = q[edges[idx].y];
//            if (idx == 7) {
//                cerr << "-------\n";
//                for (int x : cur) cerr << x << ' '; cerr << "\n";
//                cerr << "-------\n";
//            }
            function<int(int, int)> TIMEBETTER = [&](int x, int y) {
                if (dp[x] <= dp[y]) return -1;

                int64_t C = dp[x] - dp[y],
                needed = (C-1) / t[edges[idx].y] + 1;

                int p = upper_bound(A + 1, A + n1 + 1, edges[y].b) - A - 1, q = upper_bound(A + 1, A + n1 + 1, edges[x].b) - A - 1;
                if (p == q || p > q) return INT_MAX;
                if (pst::it[root[q]] - pst::it[root[p]] < needed) return INT_MAX;
                int pos = pst::bfind(needed, root[p], root[q]),
                    LAST = B[pos]+1;
                return LAST;
            };
//            if (idx == 7) {
//                cerr << TIMEBETTER(idx, 1) << ' ' << TIMEBETTER(6, 1) << " 12313\n";
//            }
            while (cur.size() >= 2 && (dp[idx] <= dp[cur.back()] ||
                TIMEBETTER(idx, cur[int(cur.size())-1]) < TIMEBETTER(cur[int(cur.size())-1], cur[int(cur.size())-2]))) cur.pop_back();

            if (!cur.empty() && dp[idx] <= dp[cur.back()]) cur.pop_back();
            cur.push_back(idx);
        }
        if (edges[i].x == 1) {
            int p = lower_bound(B + 1, B + n2 + 1, edges[i].a) - B - 1;
            dp[i] = edges[i].c + 1LL * t[edges[i].x] * (1 <= p ? pst::get(1, p, root[n1]) : 0);
        }
        deque<int> &cur = q[edges[i].x];
        function<bool(int, int)> better = [&](int x_1, int x_2) {
            if (dp[x_1] <= dp[x_2]) return true;

            int64_t C = dp[x_1] - dp[x_2];
            int64_t needed = (C-1) / t[edges[i].x] + 1;


            int p = upper_bound(A + 1, A + n1 + 1, edges[x_2].b) - A - 1, q = upper_bound(A + 1, A + n1 + 1, edges[x_1].b) - A - 1;
            if (p == q || p > q) return false;
            if (pst::it[root[q]] - pst::it[root[p]] < needed) return false;

            int pos = pst::bfind(needed, root[p], root[q]),
                LAST = B[pos]+1;
            return LAST <= edges[i].a;
        };

        if (!cur.empty()) {
            while (cur.size() > 1 && better(cur[1], cur[0])) cur.pop_front();
            int cr = cur[0];
            int p = upper_bound(A + 1, A + n1 + 1, edges[cr].b) - A - 1,
                q = lower_bound(A + 1, A + n1 + 1, edges[i].a) - A - 1,
                z = lower_bound(B + 1, B + n2 + 1, edges[i].a) - B - 1;
            dp[i] = min(dp[i], dp[cr] + 1LL * t[edges[i].x] * (1 <= z ? (pst::get(1, z, root[q]) - pst::get(1, z, root[p])) : 0) + edges[i].c);
//            cerr << i << ' ' << cr << ' ' << dp[i] << ' ' << dp[cr] << ' ' << "SDAIJD\n";
        }

        int lo = 0, hi = m+1;
        while (hi - lo > 1) {
            int mid = (lo + hi) >> 1;
            if (edges[mid].a >= edges[i].b) hi = mid;
            else lo = mid;
        }
        events[hi].insert(nnode(i));
    }

    for (int i = 1; i <= m; i++)
    if (edges[i].y == n) {
        int p = upper_bound(A + 1, A + n1 + 1, edges[i].b) - A - 1;
        int h = pst::get(1, n2, root[n1]) - pst::get(1, n2, root[p]);
        ans = min(ans, dp[i] + 1LL * t[edges[i].y] * h);
    }
//    for (int i = 1; i <= m; i++) cerr << (dp[i] >= LLONG_MAX/2 ? -1 : dp[i]) << ' '; cerr << "\n";
    return ans >= INF ? -1 : ans;
}

namespace youWontUseThis {
    ii op[maxn];
    int START[maxn], STOP[maxn];
    int64_t st[4*maxn];

    void upd(int u, int64_t d, int r = 1, int lo = 1, int hi = m) {
        if (lo == hi) {
            st[r] = min(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) : INF,
                   v > mid ? get(u, v, r<<1|1, mid+1, hi) : INF);
    }

    int64_t mainProgram() {
        sort(edges + 1, edges + m + 1, [&](const edge &a, const edge &b) {
            if (a.y != b.y) return a.y < b.y;
            return a.b < b.b;
             });
        for (int i = 1; i <= m; i++) op[i] = ii{edges[i].a, i};

        for (int i = 1; i <= n; i++) START[i] = STOP[i] = -1;
        for (int i = 1; i <= m; i++) {
            auto [x, y, a, b, c] = edges[i];
            if (START[y] == -1) START[y] = i;
            STOP[y] = i;
        }
        sort(op + 1, op + m + 1);
        for (int i = 1; i <= 4*m; i++) st[i] = INF;
        for (int i = 1; i <= m; i++) dp[i] = INF;

        for (int _ = 1; _ <= m; _++) {
            int i = op[_].se;
            auto [x, y, a, b, c] = edges[i];
            if (x == 1) {
                dp[i] = c;
                upd(i, c);
                continue;
            }
            if (START[x] == -1) continue;
            int M;
            if (1) {
                int lo = START[x]-1, hi = STOP[x]+1;
                while (hi - lo > 1) {
                    int mid = (lo + hi) >> 1;
                    if (edges[mid].b <= a) lo = mid;
                    else hi = mid;
                }
                M = lo;
            }
            if (START[x] <= M) dp[i] = min(dp[i], get(START[x], M) + c);
            upd(i, dp[i]);
        }

        int64_t ans = INF;
        for (int i = 1; i <= m; i++)
            if (edges[i].y == n) ans = min(ans, dp[i]);
        return ans >= INF ? -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) {
    if (M == 0) {
        if (N > 1) return -1;
        return 1LL * W * T[0];
    }

    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]};
    if (W == 0) return youWontUseThis::mainProgram();
	return mainProgram();
}

#ifndef EVAL
int main() {
//    if (fopen("check.inp", "r")) {
//        freopen("check.inp", "r", stdin);
//        freopen("check.out", "w", stdout);
//    }
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, W; vector<int> T, X, Y, A, B, C, L, R;
    cin >> N >> M >> W;
    T.resize(N);
    X.resize(M); Y.resize(M); A.resize(M); B.resize(M); C.resize(M);
    L.resize(W); R.resize(W);
    for (int i = 0; i < N; i++) cin >> T[i];
    for (int i = 0; i < M; i++) cin >> X[i] >> Y[i] >> A[i] >> B[i] >> C[i];
    for (int i = 0; i < W; i++) cin >> L[i] >> R[i];

    cout << solve(N, M, W, T, X, Y, A, B, C, L, R);
}
#endif
/*
5 8 10
9 4 2 24 4
0 1 17 20 5
1 2 16 18 12
1 3 27 29 13
3 4 29 30 3
1 3 25 28 10
1 2 18 20 20
0 3 1 2 22
1 0 20 26 17
26 30
29 30
29 30
27 28
17 27
21 24
6 15
12 27
3 3
13 26

40
*/

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