Submission #594474

#	Time	Username	Problem	Language	Result	Execution time	Memory
594474		Vanilla	Pinball (JOI14_pinball)	C++17	51 / 100	1060 ms	401980 KiB

pinball

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

struct node {
    int64 v;

    node* left;
    node* right;

    node(int64 _v): v(_v) {};
    
    void extend() {
        if (left != NULL) return;
        left = new node(1e15);
        right = new node(1e15);
    }

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

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

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