Submission #1271597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271597		lechaa	Pinball (JOI14_pinball)	C++20	0 / 100	0 ms	324 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));
}

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);
    vector<int> dp(d.size(), 1e18);
    update(1, 0, d.size()-1, 0, 0);
    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);
        if(j == 1e18) continue;
        dp[c] = min(dp[c], j + x[i][3]);
        update(1, 0, d.size()-1, c, dp[c]);
    }
    vector<int> dp1(d.size(), 1e18);
    t.clear();
    t.resize(d.size(), 1e18);
    update(1, 0, d.size()-1, d.size()-1, 0);
    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, 0, r);
        if(j == 1e18) continue;
        dp1[c] = min(dp1[c], j + x[i][3]);
        update(1, 0, d.size()-1, c, dp1[c]);
    }
    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]);
        mn = min(mn, dp[c] + dp1[c] - x[i][3]);
    }
    if(mn == 1e18){
        mn = -1;
    }
    cout << mn << "\n";
    return 0;
}

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