Submission #594467

#	Time	Username	Problem	Language	Result	Execution time	Memory
594467		Vanilla	Pinball (JOI14_pinball)	C++17	51 / 100	994 ms	524288 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 1e5 + 2;
int n,m;

struct node {
    int l,r;
    int64 v;

    node* left;
    node* right;

    node(int _l, int _r, int64 _v): l(_l), r(_r), v(_v) {};
    
    void extend() {
        if (left != NULL) return;
        int mid = (l + r) / 2;
        left = new node(l, mid, 1e15);
        right = new node(mid + 1, r, 1e15);
    }

    int64 query (int il, int ir) {
        if (il <= l && r <= ir) return v;
        if (l > ir || r < il) return 1e15;
        extend();
        return min(left->query(il, ir), right->query(il, ir));
    }

    void update (int x, int64 nval) {
        if (l == r && l == x) return void(v = min(v, nval));
        if (l > x || r < x) return;
        extend();
        left->update(x, nval);
        right->update(x, nval);
        v = min(left->v, right->v);
    }
};
 
 
int main() {
    cin >> n >> m;
    node* lf = new node(0, m + 1, 1e15);
    node* rt = new node(0, m + 1, 1e15);
    int64 rs = 1e15;
    lf->update(1, 0);
    rt->update(m, 0);
    for (int i = 0; i < n; i++){
        int64 a,b,c,cost;
        cin >> a >> b >> c >> cost;
        int64 p1 = lf->query(a,b);
        int64 p2 = rt->query(a,b);
        rs = min(rs, p1 + p2 + cost);
        lf->update(c, p1 + cost);
        rt->update(c, p2 + cost);
    }
    cout << (rs >= 1e15 ? -1: rs);
}

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