Submission #500966

#	Time	Username	Problem	Language	Result	Execution time	Memory
500966		n00bie_1004	Pinball (JOI14_pinball)	C++17	100 / 100	606 ms	47596 KiB

pinball

#include <bits/stdc++.h>
typedef long long int ll; 

using namespace std;

struct pr {
    ll l, r, mid, cost; 
}; 
struct segtree {
    ll n;
    vector<ll> st; 

    ll merge(ll a, ll b){
        return min(a, b);
    } 

    void init(ll x){
        n = x; 
        st.assign(4 * n, 1e18); 
    }

    void update1(ll idx, ll l, ll r, ll pos, ll val){
        if(l != r){
            ll mid = l + (r - l) / 2; 
            if(pos <= mid)
                update1(2 * idx, l, mid, pos, val);
            else 
                update1(2 * idx + 1, mid + 1, r, pos, val);
            st[idx] = merge(st[2 * idx], st[2 * idx + 1]); 
        }
        else {
            st[idx] = min(st[idx], val); 
            return;
        }
    }
    void update2(ll pos, ll val){
        update1(1, 0, n - 1, pos, val);
    } 

    ll query1(ll idx, ll r_l, ll r_r, ll q_l, ll q_r){ 
        if(q_r >= r_r && q_l <= r_l) 
            return st[idx];
        if(q_l > r_r || q_r < r_l) 
            return 1e18; 
        ll mid = r_l + (r_r - r_l) / 2; 
        return merge(query1(2 * idx, r_l, mid, q_l, q_r), query1(2 * idx + 1, mid + 1, r_r, q_l, q_r)); 
    }
    ll query2(ll q_l, ll q_r){
        return query1(1, 0, n - 1, q_l, q_r);
    } 
};
int main(){ 
    ios_base::sync_with_stdio(false); cin.tie(NULL); 
    ll m, n;
    cin >> m >> n;
    vector<pr> v(m);  
    set<ll> s; 
    s.insert(0); 
    for(ll i=0;i<m;i++){
        cin >> v[i].l >> v[i].r >> v[i].mid >> v[i].cost;
        --v[i].l; 
        s.insert(v[i].l); 
        --v[i].mid; 
        s.insert(v[i].mid);
        --v[i].r; 
        s.insert(v[i].r); 
    }
    s.insert(n - 1);
    map<ll, ll> pos;  
    ll new_pos = 0;
    for(auto x : s)
        pos[x] = new_pos++; 
    for(ll i=0;i<m;i++){
        v[i].l = pos[v[i].l]; 
        v[i].mid = pos[v[i].mid];
        v[i].r = pos[v[i].r]; 
    }
    n = pos[n - 1];
    n++;  
    segtree ST; 
    vector<ll> dpL(m, 1e18); 
    ST.init(n); 
    for(ll i=0;i<m;i++){
        if(v[i].l == 0){
            dpL[i] = v[i].cost;
            ST.update2(v[i].mid, dpL[i]); 
            continue; 
        }
        ll val = ST.query2(v[i].l, v[i].r); 
        dpL[i] = min(dpL[i], val + v[i].cost); 
        ST.update2(v[i].mid, dpL[i]); 
    }
    vector<ll> dpR(m, 1e18); 
    ST.init(n);
    for(ll i=0;i<m;i++){
        if(v[i].r == n - 1){
            dpR[i] = v[i].cost; 
            ST.update2(v[i].mid, dpR[i]); 
            continue; 
        }
        ll val = ST.query2(v[i].l, v[i].r); 
        dpR[i] = min(dpR[i], val + v[i].cost); 
        ST.update2(v[i].mid, dpR[i]); 
    }
    ll ans = 1e18; 
    for(ll i=0;i<m;i++)
        ans = min(ans, dpL[i] + dpR[i] - v[i].cost);
    if(ans >= 1e18)
        ans = -1;
    cout << ans << "\n"; 
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n"; 
}

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