Submission #299851

#	Time	Username	Problem	Language	Result	Execution time	Memory
299851		nickmet2004	Pinball (JOI14_pinball)	C++11	100 / 100	471 ms	55308 KiB

pinball

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll INF = 1e18;
int n,m;
struct ST{
    struct Node{
        int l = -1 , r = -1;
        ll val = INF;
    };
    vector<Node> T = vector<Node>(1);
    void extend(int &pos){
        if(pos != -1) return;
        pos = T.size();
        T.emplace_back();
    }
    void W(int pos){
        T[pos].val = INF;
        int l = T[pos].l , r = T[pos].r;
        if(l != -1) T[pos].val = min(T[pos].val , T[l].val);
        if(r != -1) T[pos].val = min(T[pos].val , T[r].val);
    }
    void upd(int idx , ll v , int l = 0 , int r = m - 1 , int pos = 0){
        if(idx < l || idx > r) return;
        if(l == r){
            T[pos].val = min(T[pos].val , v);
            return;
        }
        int mid = (l + r) >> 1;
        if(idx <= mid){
            extend(T[pos].l);
            upd(idx , v , l , mid , T[pos].l);
        } else {
            extend(T[pos].r);
            upd(idx , v , mid + 1 , r , T[pos].r);
        }
        W(pos);
    }
    ll get(int L , int R , int l = 0,  int r= m - 1 , int pos = 0){
        if(r < L || R < l || pos == -1) return INF;
        if(L <= l && r <= R) return T[pos].val;
        int mid = (l + r) >> 1;
        return min(get(L , R , l , mid , T[pos].l) , get(L , R , mid + 1 , r , T[pos].r) );
    }
}L , R;
int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    vector<int> A(n) , B(n) , C(n) , D(n);
    for(int i = 0; i < n; ++i) {cin >> A[i] >> B[i] >> C[i] >> D[i]; --A[i]; --B[i]; --C[i];}
    L.upd(0 , 0); R.upd(m - 1 , 0);
    ll ans = INF;
    for(int i = 0; i < n; ++i){
        int l = A[i] , r = B[i] , center = C[i] , cost = D[i];
        ll left = L.get(l , r) , right = R.get(l , r);
        ans = min(ans, left + right + cost);
        L.upd(center , left + cost); R.upd(center , right + cost);
    }
    if(ans == INF) ans = -1;
    cout << ans;
}

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