Submission #854143

#	Time	Username	Problem	Language	Result	Execution time	Memory
854143		Desh03	Pinball (JOI14_pinball)	C++17	11 / 100	195 ms	524288 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

const long long INF = 1e18;

template<typename T>
    struct SegmentTree {
        vector<T> st;
        int n;
        SegmentTree(int n_) : n(n_) {
            st.resize(n << 1, INF);
        }
        void update(int i, T x) {
            i += n;
            st[i] = min(st[i], x);
            while (i >>= 1) st[i] = min(st[i << 1], st[i << 1 | 1]);
        }
        T query(int l, int r) {
            T mn = INF;
            for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
                if (l & 1) mn = min(mn, st[l++]);
                if (r & 1) mn = min(mn, st[--r]);
            }
            return mn;
        }
    };

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int m, n;
    cin >> m >> n;
    SegmentTree<long long> l(n), r(n);
    long long ans = INF;
    while (m--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        --a, --c;
        if (!a && b == n) {
            ans = min(ans, (long long) d);
        } else if (!a) {
            long long y = r.query(a, b);
            if (y != INF) {
                ans = min(ans, d + y);
                r.update(c, d + y);
            }
            l.update(c, d);
        } else if (b == n) {
            long long x = l.query(a, b);
            if (x != INF) {
                ans = min(ans, x + d);
                l.update(c, x + d);
            }
            r.update(c, d);
        } else {
            long long x = l.query(a, b), y = r.query(a, b);
            ans = min(ans, x + y + d);
            if (x != INF) {
                l.update(c, x + d);
            }
            if (y != INF) {
                r.update(c, y + d);
            }
        }
    }
    cout << (ans == INF ? -1 : ans);
    return 0;
}

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