제출 #1271599

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271599		lechaa	Pinball (JOI14_pinball)	C++20	11 / 100	1 ms	328 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<int> d;

int idx(int k){
    auto it = lower_bound(d.begin(), d.end(), k);
    return (it - d.begin());
}

vector<int> t;

void update(int i, int l, int r, int i1, int v){
    if(l == r){
        t[i] = v;
        return;
    }
    int mid = (l+r)/2;
    if(i1 <= mid){
        update(i*2, l, mid, i1, v);
    }else{
        update(i*2+1, mid+1, r, i1, v);
    }
    t[i] = min(t[i*2], t[i*2+1]);
}

int query(int i, int l, int r, int l1, int r1){
    if(l > r1 || l1 > r){
        return 1e18;
    }
    if(l1 <= l && r1 >= r){
        return t[i];
    }
    int mid = (l + r)/2;
    return min(query(i*2, l, mid, l1, r1), query(i*2+1, mid+1, r, l1, r1));
}


vector<int> t1;

void update1(int i, int l, int r, int i1, int v){
    if(l == r){
        t1[i] = v;
        return;
    }
    int mid = (l+r)/2;
    if(i1 <= mid){
        update1(i*2, l, mid, i1, v);
    }else{
        update1(i*2+1, mid+1, r, i1, v);
    }
    t1[i] = min(t1[i*2], t1[i*2+1]);
}

int query1(int i, int l, int r, int l1, int r1){
    if(l > r1 || l1 > r){
        return 1e18;
    }
    if(l1 <= l && r1 >= r){
        return t1[i];
    }
    int mid = (l + r)/2;
    return min(query1(i*2, l, mid, l1, r1), query1(i*2+1, mid+1, r, l1, r1));
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int m, n; cin >> m >> n;
    vector<array<int, 4>> x(m); 
    for(int i = 0; i < m; i++){
        cin >> x[i][0] >> x[i][1] >> x[i][2] >> x[i][3];
        d.push_back(x[i][0]);
        d.push_back(x[i][1]);
        d.push_back(x[i][2]);
    }
    d.push_back(1);
    d.push_back(n);
    sort(d.begin(), d.end());
    d.erase(unique(d.begin(), d.end()), d.end());
    t.resize(d.size()*4, 1e18);
    t1.resize(d.size()*4, 1e18);
    vector<int> dp(d.size(), 1e18);
    update(1, 0, d.size()-1, 0, 0);
    t1.resize(d.size()*4, 1e18);
    vector<int> dp1(d.size(), 1e18);
    update1(1, 0, d.size()-1, d.size()-1, 0);
    int mn = 1e18;
    for(int i = 0; i < m; i++){
        int l, r;
        l = idx(x[i][0]);
        r = idx(x[i][1]);
        int c = idx(x[i][2]);
        int j = query(1, 0, d.size()-1, l, d.size()-1);
        int raveluk = -1;
        if(j != 1e18){
            dp[c] = min(dp[c], j + x[i][3]);
            update(1, 0, d.size()-1, c, dp[c]);
            raveluk = j;
        }
        j = query1(1, 0, d.size()-1, 0, r);
        if(j == 1e18) continue;
        dp1[c] = min(dp1[c], j + x[i][3]);
        update1(1, 0, d.size()-1, c, dp1[c]);
        int h = j  + x[i][3];
        if(raveluk == -1) continue;
        mn = min(mn, raveluk + h);
    }
    if(mn == 1e18){
        mn = -1;
    }
    cout << mn << "\n";
    return 0;
}

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