Submission #856980

#	Time	Username	Problem	Language	Result	Execution time	Memory
856980		thanh913	Pinball (JOI14_pinball)	C++14	51 / 100	170 ms	21624 KiB

pinball

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

#define fi first
#define se second
#define ll long long
#define int long long

const int N = 1e5+5;

struct interval {
    int l, r, pos, cost;
};

//-------------------------------
interval a[N];
int n, len;

vector<int> vals;

struct SegmentTree {
    ll seg[N*8];
    SegmentTree() {
        memset(seg, 0x3f, sizeof(seg));
    }

    void update(int pos, ll val, int l = 0, int r = vals.size() - 1, int id = 1) {
        if (l > pos || r < pos) return;
        if (l == r) {
            seg[id] = min(seg[id], val);
            return;
        }
        int mid = (l+r) / 2;
        update(pos, val, l, mid, id*2);
        update(pos, val, mid+1, r, id*2 + 1);
        seg[id] = min(seg[id*2], seg[id*2 + 1]);
    }

    ll get(int u, int v, int l = 0, int r = vals.size() - 1, int id = 1) {
        if (l > v || r < u) return 4e18;
        if (l >= u && r <= v) return seg[id];
        int mid = (l+r) / 2;
        return min(get(u, v, l, mid, id*2),
                   get(u, v, mid+1, r, id*2 + 1));
    }
} lTree, rTree;

int idx(int val) {
    return lower_bound(vals.begin(), vals.end(), val) - vals.begin();
};

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> len;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].l >> a[i].r >> a[i].pos >> a[i].cost;
        vals.push_back(a[i].l);
        vals.push_back(a[i].r);
    }
    vals.push_back(1); vals.push_back(len);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    for (int i = 1; i <= n; i++) {
        a[i].l = idx(a[i].l); a[i].r = idx(a[i].r); a[i].pos = idx(a[i].pos);
    }

    ll ans = 4e18;
    lTree.update(idx(1), 0); rTree.update(idx(len), 0);
    for (int i = 1; i <= n; i++) {
        ll v1 = lTree.get(a[i].l, a[i].r) + a[i].cost;
        ll v2 = rTree.get(a[i].l, a[i].r) + a[i].cost;
        ans = min(ans, v1+v2 - a[i].cost);
        lTree.update(a[i].pos, v1);
        rTree.update(a[i].pos, v2);
    }
    cout << (ans > 1e18 ? -1 : ans);
}

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