Submission #1257195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257195		coin_	Pinball (JOI14_pinball)	C++20	0 / 100	0 ms	320 KiB

pinball

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

struct SegTree {
    int n;
    vector<ll> st;
    SegTree(int _n=0){ init(_n); }
    void init(int _n){
        n = max(1, _n);
        st.assign(4*n+5, INF);
    }
    void point_min_update(int id, int l, int r, int pos, ll val){
        if(l == r){
            st[id] = min(st[id], val);
            return;
        }
        int mid = (l + r) >> 1;
        if(pos <= mid) point_min_update(id<<1, l, mid, pos, val);
        else point_min_update(id<<1|1, mid+1, r, pos, val);
        st[id] = min(st[id<<1], st[id<<1|1]);
    }
    void point_min_update(int pos, ll val){ point_min_update(1, 1, n, pos, val); }

    ll range_min(int id, int l, int r, int ql, int qr){
        if(ql > r || qr < l) return INF;
        if(ql <= l && r <= qr) return st[id];
        int mid = (l + r) >> 1;
        return min(range_min(id<<1, l, mid, ql, qr),
                   range_min(id<<1|1, mid+1, r, ql, qr));
    }
    ll range_min(int l, int r){
        if(l > r) return INF;
        l = max(l, 1); r = min(r, n);
        if(l > r) return INF;
        return range_min(1, 1, n, l, r);
    }
    ll get_point(int pos){ return range_min(pos, pos); }
};

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

    int N, M;
    if(!(cin >> N >> M)) return 0;

    struct Dev { ll A,B,C,D; };
    vector<Dev> dev(M);
    vector<ll> coords;
    coords.push_back(1);
    coords.push_back(N);
    for(int i=0;i<M;i++){
        cin >> dev[i].A >> dev[i].B >> dev[i].C >> dev[i].D;
        coords.push_back(dev[i].A);
        coords.push_back(dev[i].B);
        coords.push_back(dev[i].C);
    }

    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()), coords.end());
    auto idx = [&](ll x){ return int(lower_bound(coords.begin(), coords.end(), x) - coords.begin()) + 1; };
    int K = (int)coords.size();

    vector<int> A(M), B(M), C(M);
    vector<ll> D(M);
    for(int i=0;i<M;i++){
        A[i] = idx(dev[i].A);
        B[i] = idx(dev[i].B);
        C[i] = idx(dev[i].C);
        D[i] = dev[i].D;
    }
    int startL = idx(1), startR = idx(N);

    // Forward pass for L[i]
    vector<ll> L(M, INF), Rv(M, INF); // Rv will store right-pass results
    {
        SegTree seg(K);
        seg.point_min_update(startL, 0);
        for(int i=0;i<M;i++){
            ll best = seg.range_min(A[i], B[i]);
            if(best < INF){
                ll cand = best + D[i];
                seg.point_min_update(C[i], cand);
            }
            L[i] = seg.get_point(C[i]);
        }
    }

    // Backward pass for R[i]
    {
        SegTree seg(K);
        seg.point_min_update(startR, 0);
        for(int i=M-1;i>=0;i--){
            ll best = seg.range_min(A[i], B[i]);
            if(best < INF){
                ll cand = best + D[i];
                seg.point_min_update(C[i], cand);
            }
            Rv[i] = seg.get_point(C[i]);
        }
    }

    ll ans = INF;
    for(int i=0;i<M;i++){
        if(L[i] >= INF || Rv[i] >= INF) continue;
        ans = min(ans, L[i] + Rv[i] - D[i]);
    }
    if(ans >= INF) cout << -1 << '\n';
    else cout << ans << '\n';
    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 49