oj.uz

답안 #500962

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
500962 2022-01-01T18:20:31 Z n00bie_1004 Pinball (JOI14_pinball) C++14
0 / 100
 1 ms 308 KB 
#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, arr;  

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

    void init(ll x, vector<ll> y){
        n = x; 
        arr = y; 
        st.assign(4 * n, 1e18); 
        build(1, 0, n - 1);
    }

    void build(ll idx, ll l, ll r){
        if(l != r){
            ll mid = l + (r - l) / 2; 
            build(2 * idx, l, mid); 
            build(2 * idx + 1, mid + 1, r); 
            st[idx] = merge(st[2 * idx], st[2 * idx + 1]); 
        }
        else {
            st[idx] = min(st[idx], arr[l]); 
            return;
        }
    }

    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(m, dpL); 
    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(m, dpR);
    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
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -