Submission #1203018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203018		zeta7532	Train (APIO24_train)	C++20	In queue	0 ms	0 KiB

train

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL<<60);

// ---- Persistent Segment Tree for point-add & range-sum ----
struct PST {
    struct Node { int l, r, sum; };
    vector<Node> st;
    int N;
    PST(int _N): N(_N) {
        st.reserve(N * 20);
        st.push_back({0,0,0}); // dummy
    }
    // build empty tree on [l..r]
    int build(int l, int r) {
        int id = st.size();
        st.push_back({0,0,0});
        if (l < r) {
            int m = (l + r) >> 1;
            st[id].l = build(l, m);
            st[id].r = build(m+1, r);
        }
        return id;
    }
    // point add: create new version from prev, add v at pos p
    int update(int prev, int l, int r, int p, int v) {
        int id = st.size();
        st.push_back(st[prev]);
        if (l == r) {
            st[id].sum += v;
        } else {
            int m = (l + r) >> 1;
            if (p <= m)
                st[id].l = update(st[prev].l, l, m, p, v);
            else
                st[id].r = update(st[prev].r, m+1, r, p, v);
            st[id].sum = st[ st[id].l ].sum + st[ st[id].r ].sum;
        }
        return id;
    }
    // range sum on [ql..qr]
    int query(int id, int l, int r, int ql, int qr) const {
        if (!id || qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return st[id].sum;
        int m = (l + r) >> 1;
        return query(st[id].l, l, m, ql, qr)
             + query(st[id].r, m+1, r, ql, qr);
    }
};

// ---- input train / meal structs ----
struct Train {
    int x, y;
    int a, b;
    ll c;
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, w;
    cin >> n >> m >> w;
    vector<ll> t(n);
    for(int i = 0; i < n; i++) {
        cin >> t[i];
    }

    vector<pair<int,int>> meals(w);
    for(int i = 0; i < w; i++){
        cin >> meals[i].first >> meals[i].second;
    }

    vector<Train> trains(m);
    for(int i = 0; i < m; i++){
        cin >> trains[i].x
            >> trains[i].y
            >> trains[i].a
            >> trains[i].b
            >> trains[i].c;
    }

    // 1) 時刻の座標圧縮準備
    vector<int> allT;
    allT.reserve(2*m + 2*w + 1);
    allT.push_back(0);
    for(auto &tr : trains){
        allT.push_back(tr.a);
        allT.push_back(tr.b);
    }
    for(auto &me : meals){
        allT.push_back(me.first);
        allT.push_back(me.second);
    }
    sort(allT.begin(), allT.end());
    allT.erase(unique(allT.begin(), allT.end()), allT.end());
    auto comp = [&](int x){
        return int(lower_bound(allT.begin(), allT.end(), x) - allT.begin());
    };
    int Tsz = allT.size();

    // 2) meals を r_comp ごとにバケット化
    vector<vector<int>> meals_at_r(Tsz);
    for(auto &me : meals){
        int lc = comp(me.first);
        int rc = comp(me.second);
        meals_at_r[rc].push_back(lc);
    }

    // 3) 永続セグ木の構築：バージョン v[i] は「r ≤ i の meal を全部追加済み」
    PST pst(Tsz);
    vector<int> version(Tsz);
    version[0] = pst.build(0, Tsz-1);
    for(int lpos : meals_at_r[0]){
        version[0] = pst.update(version[0], 0, Tsz-1, lpos, 1);
    }
    for(int i = 1; i < Tsz; i++){
        version[i] = version[i-1];
        for(int lpos : meals_at_r[i]){
            version[i] = pst.update(version[i], 0, Tsz-1, lpos, 1);
        }
    }

    // g(b, a) を計算：区間 (b, a) に完全包含される meal の数
    auto get_g = [&](int b, int a){
        int bc = comp(b);
        int ac = comp(a);
        if (ac == 0) return 0;
        // r < a に登録済みの全点数
        int total = pst.query(version[ac-1], 0, Tsz-1, 0, Tsz-1);
        // うち l ≤ b の点数
        int bad   = pst.query(version[ac-1], 0, Tsz-1, 0, bc);
        return total - bad;
    };

    // 4) 列車を departure 時刻 a の昇順でソート
    vector<int> idx(m);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(),
         [&](int i, int j){ return trains[i].a < trains[j].a; });

    // DP 配列、ヒープ＆Deque 構造
    vector<ll> dp(m, INF);
    vector< priority_queue<pair<int,int>,
        vector<pair<int,int>>, greater<>> > heap(n);
    vector< deque<int> > dq(n);

    // 初期状態：planet 0 に時刻0、idx = -1 を投げておく
    heap[0].push({0, -1});
    auto get_dp = [&](int j){
        return (j < 0 ? 0LL : dp[j]);
    };
    auto get_b  = [&](int j){
        return (j < 0 ? 0    : trains[j].b);
    };

    ll ans = INF;
    // 5) メインループ：departure 時刻昇順で列車 i を処理
    for(int _k = 0; _k < m; _k++){
        int i = idx[_k];
        int p = trains[i].x;
        int ai = trains[i].a;

        // ■ step1: 到着済み j を heap[p] から dq[p] へ流し込む
        auto &hp = heap[p];
        auto &dq_p = dq[p];
        while(!hp.empty() && hp.top().first <= ai){
            int j = hp.top().second;
            hp.pop();
            // 四辺形不等式にもとづく pop-back 条件
            while(dq_p.size() >= 2){
                int j2 = dq_p.back();
                int j1 = dq_p[dq_p.size()-2];
                ll lhs = get_dp(j2)
                      + (ll)get_g(get_b(j2), ai) * t[p];
                ll rhs = get_dp(j1)
                      + (ll)get_g(get_b(j1), ai) * t[p];
                if (lhs >= rhs) dq_p.pop_back();
                else break;
            }
            dq_p.push_back(j);
        }

        // ■ step2: dq[p].front() が最適遷移元
        if (!dq_p.empty()){
            int j = dq_p.front();
            dp[i] = get_dp(j)
                  + (ll)get_g(get_b(j), ai) * t[p]
                  + trains[i].c;
            if (trains[i].y == n-1)
                ans = min(ans, dp[i]);
        }

        // ■ step3: i を到着 heap に追加
        heap[trains[i].y].push({trains[i].b, i});
    }

    if (ans >= INF/2) ans = -1;
    cout << ans << "\n";
    return 0;
}