oj.uz

Submission #245297

# Submission time Handle Problem Language Result Execution time Memory
245297 2020-07-06T01:33:02 Z thecodingwizard Pinball (JOI14_pinball) C++11
0 / 100
 4 ms 256 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll inf = 1e18;

map<int, int> cc;

struct SegTree {
    vector<ll> st;
    int n;
    void init(int _n) {
        n = _n; st.assign(2*n, inf);
    }
    void upd(int p, ll v) {
        st[p += n] = v;
        for (p /= 2; p; p /= 2) st[p] = min(st[2*p], st[2*p+1]);
    }
    ll qry(int l, int r) {
        ll a = inf;
        for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
            if (l&1) a = min(a, st[l++]);
            if (r&1) a = min(a, st[--r]);
        }
        return a;
    }
} lft, rht;

int main() {
    int m, n; cin >> m >> n;
    int L[m], R[m], T[m], C[m];
    for (int i = 0; i < m; i++) cin >> L[i] >> R[i] >> T[i] >> C[i];

    vector<int> pts;
    for (int i = 0; i < m; i++) {
        pts.push_back(L[i]);
        pts.push_back(R[i]);
        pts.push_back(T[i]);
    }
    sort(pts.begin(), pts.end());
    pts.erase(unique(pts.begin(), pts.end()), pts.end());

    int np = pts.size();
    lft.init(np); rht.init(np);
    for (int i = 0; i < np; i++) {
        cc[pts[i]] = i;
    }

    ll dpLeft[m], dpRight[m];
    for (int i = 0; i < m; i++) {
        dpLeft[i] = dpRight[i] = inf;

        if (L[i] == 1) dpLeft[i] = C[i];
        if (R[i] == n) dpRight[i] = C[i];

        dpLeft[i] = min(dpLeft[i], C[i] + lft.qry(cc[L[i]], cc[R[i]]));
        dpRight[i] = min(dpRight[i], C[i] + rht.qry(cc[L[i]], cc[R[i]]));

        lft.upd(cc[T[i]], dpLeft[i]);
        rht.upd(cc[T[i]], dpRight[i]);
    }

    ll opt = inf;

    for (int i = 0; i < m; i++) {
        opt = min(opt, dpLeft[i] + dpRight[i] - C[i]);
    }

    if (opt == inf) cout << -1 << endl;
    else cout << opt << endl;

    return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -