Submission #441656

#	Time	Username	Problem	Language	Result	Execution time	Memory
441656		JovanB	Pinball (JOI14_pinball)	C++17	100 / 100	539 ms	31164 KiB

pinball

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

using ll = long long;
using ld = long double;

map <int, int> cval;

const int MAXN = 100000;

ll seg[12*MAXN+50];

const ll INF = 1000000000000000LL;

void init(int node, int l, int r){
    seg[node] = INF;
    if(l == r) return;
    int mid = (l+r)/2;
    init(node*2, l, mid);
    init(node*2+1, mid+1, r);
}

void upd(int node, int l, int r, int x, ll val){
    if(l == r){
        seg[node] = min(seg[node], val);
        return;
    }
    int mid = (l+r)/2;
    if(x <= mid) upd(node*2, l, mid, x, val);
    else upd(node*2+1, mid+1, r, x, val);
    seg[node] = min(seg[node*2], seg[node*2+1]);
}

ll query(int node, int l, int r, int tl, int tr){
    if(tl > r || l > tr) return INF;
    if(tl <= l && r <= tr) return seg[node];
    int mid = (l+r)/2;
    return min(query(node*2, l, mid, tl, tr), query(node*2+1, mid+1, r, tl, tr));
}

ll dp1[MAXN+5];
ll dpn[MAXN+5];
int a[MAXN+5];
int b[MAXN+5];
int c[MAXN+5];
ll cost[MAXN+5];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, m;
    cin >> n >> m;
    vector <int> cvec;
    for(int i=1; i<=n; i++){
        cin >> a[i] >> b[i] >> c[i] >> cost[i];
        cvec.push_back(a[i]);
        cvec.push_back(b[i]);
        cvec.push_back(c[i]);
    }
    cvec.push_back(1);
    cvec.push_back(m);
    sort(cvec.begin(), cvec.end());
    int maxv = 0;
    for(auto c : cvec) if(!cval[c]) cval[c] = ++maxv;
    init(1, 1, maxv);
    upd(1, 1, maxv, cval[1], 0);
    for(int i=1; i<=n; i++){
        a[i] = cval[a[i]];
        b[i] = cval[b[i]];
        c[i] = cval[c[i]];
    }
    for(int i=1; i<=n; i++){
        dp1[i] = query(1, 1, maxv, a[i], b[i]);
        upd(1, 1, maxv, c[i], dp1[i] + cost[i]);
    }
    init(1, 1, maxv);
    upd(1, 1, maxv, cval[m], 0);
    for(int i=1; i<=n; i++){
        dpn[i] = query(1, 1, maxv, a[i], b[i]);
        upd(1, 1, maxv, c[i], dpn[i] + cost[i]);
    }
    ll res = INF;
    for(int i=1; i<=n; i++){
        res = min(res, cost[i] + dp1[i] + dpn[i]);
    }
    cout << (res == INF ? -1 : res) << "\n";
    return 0;
}

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