제출 #1177918

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177918		trashaccount	Train (APIO24_train)	C++20	10 / 100	73 ms	37056 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vi vector <int>
#define isz(a) (int)(a).size()

const int NM = 2e5;
const ll inf = 1e18;

namespace subtask1{
    int N, M, W, f[2005][2005];
    vi T, X, Y, A, B, C, L, R, od;
    ll d[2005];

    int calc(int x, int y){
        if (x > y) return 0;
        return f[x][y];
    }
    ll solve(int _N, int _M, int _W, vi _T, vi _X, vi _Y, vi _A, vi _B, vi _C, vi _L, vi _R){
        N = _N, M = _M, W = _W;
        T = _T, X = _X, Y = _Y, A = _A, B = _B, C = _C, L = _L, R = _R;

        od.clear();
        for (int i = 0; i < M; i++) od.push_back(i);
        sort(od.begin(), od.end(), [&](int i, int j){
            return B[i] < B[j];
        });

        memset(f, 0, sizeof(f));
        for (int i = 0; i < W; i++) f[L[i]][R[i]]++;
        
        for (int i = 2000; i >= 0; i--)
            for (int j = i+1; j <= 2000; j++)
                f[i][j] += f[i+1][j]+f[i][j-1]-f[i+1][j-1];

        for (int t1 = 0; t1 < M; t1++){
            int i = od[t1];
            if (X[i] == 0) d[i] = 1LL*calc(0, A[i]-1)*T[X[i]]+C[i];
            else d[i] = +inf;
            for (int t2 = 0; t2 < t1; t2++){
                int j = od[t2];
                if (Y[j] != X[i]) continue;
                if (B[j] > A[i]) continue;
                d[i] = min(d[i], d[j]+1LL*calc(B[j]+1, A[i]-1)*T[X[i]]+C[i]);
            }
        }
        ll ans = +inf;
        for (int t = 0; t < M; t++){
            if (Y[t] != N-1) continue;
            ans = min(ans, d[t]+1LL*calc(B[t]+1, NM)*T[N-1]);
        }
        if (ans == +inf) return -1;
        return ans;
    }
}

namespace subtask2{
    struct segtree{
        vector <ll> data;
        void reset(int n){
            data.assign(4*n+5, +inf);
        }
        void update(int id, int l, int r, int i, ll val){
            if (i < l || i > r) return;
            if (l == r){
                data[id] = min(data[id], val);
                return;
            }
            int mid = (l+r)/2;
            update(2*id, l, mid, i, val);
            update(2*id+1, mid+1, r, i, val);
            data[id] = min(data[2*id], data[2*id+1]);
        }
        ll get(int id, int l, int r, int u, int v){
            if (u > v || v < l || u > r) return +inf;
            if (l >= u && r <= v) return data[id];
            int mid = (l+r)/2;
            return min(get(2*id, l, mid, u, v), get(2*id+1, mid+1, r, u, v)); 
        }
    } ST[NM+5];

    int N, M, W;
    vi T, X, Y, A, B, C, L, R, od;
    ll d[NM+5];
    vector <int> arr[NM+5];
    int sz[NM+5];

    ll solve(int _N, int _M, int _W, vi _T, vi _X, vi _Y, vi _A, vi _B, vi _C, vi _L, vi _R){
        N = _N, M = _M, W = _W;
        T = _T, X = _X, Y = _Y, A = _A, B = _B, C = _C, L = _L, R = _R;

        for (int i = 0; i < N; i++) arr[i].clear();

        for (int i = 0; i < M; i++){
            arr[X[i]].push_back(A[i]);
            arr[Y[i]].push_back(B[i]);
        }
        for (int i = 0; i < N; i++){
            sort(arr[i].begin(), arr[i].end());
            arr[i].erase(unique(arr[i].begin(), arr[i].end()), arr[i].end());
            sz[i] = isz(arr[i]);
            ST[i].reset(sz[i]);
        }

        od.clear();
        for (int i = 0; i < M; i++) od.push_back(i);
        sort(od.begin(), od.end(), [&](int i, int j){
            return B[i] < B[j];
        });

        for (int t = 0; t < M; t++){
            int i = od[t];
            if (X[i] == 0) d[i] = C[i];
            else{
                int p = lower_bound(arr[X[i]].begin(), arr[X[i]].end(), A[i])-arr[X[i]].begin()+1;
                d[i] = ST[X[i]].get(1, 1, sz[X[i]], 1, p)+C[i];
            }

            int q = lower_bound(arr[Y[i]].begin(), arr[Y[i]].end(), B[i])-arr[Y[i]].begin()+1;
            ST[Y[i]].update(1, 1, sz[Y[i]], q, d[i]);
        }
        ll ans = +inf;
        for (int t = 0; t < M; t++){
            if (Y[t] != N-1) continue;
            ans = min(ans, d[t]);
        }
        if (ans == +inf) return -1;
        return ans;
    }
}

ll solve(int N, int M, int W, vi T, vi X, vi Y, vi A, vi B, vi C, vi L, vi R){
    if (W == 0) return subtask2::solve(N, M, W, T, X, Y, A, B, C, L, R);
    return subtask1::solve(N, M, W, T, X, Y, A, B, C, L, R);
}

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