Submission #1196991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196991		og_matveychick1	Pinball (JOI14_pinball)	C++20	100 / 100	180 ms	25612 KiB

pinball

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;

struct ST {
    vector<ll> t;
    ll n;

    ST(ll n) : n(n), t(4 * n, 1e18) {}

    void update(ll p, ll x) {
        update(1, 0, n, p, x);
    }

    void update(ll v, ll l, ll r, ll p, ll x) {
        if (l > p || r <= p) return;
        if (l + 1 == r) {
            t[v] = min(t[v], x);
            return;
        }
        ll m = (l + r) / 2;
        update(v * 2, l, m, p, x);
        update(v * 2 + 1, m, r, p, x);
        t[v] = min(t[v * 2], t[v * 2 + 1]);
    }

    ll get(ll l, ll r) {
        return get(1, 0, n, l, r);
    }

    ll get(ll v, ll l, ll r, ll L, ll R) {
        if (l >= R || r <= L) return 1e18;
        if (l >= L && r <= R) return t[v];
        ll m = (l + r) / 2;
        return min(get(v * 2, l, m, L, R), get(v * 2 + 1, m, r, L, R));
    }
};

const ll N = 1e6;

ll m, n, a[N], c[N], b[N], d[N], p[N];
vector<ll> s;


signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> m >> n;
    s = {1, n};
    for (ll i = 0; i < m; i++)
        cin >> a[i] >> b[i] >> c[i] >> d[i], s.push_back(a[i]), s.push_back(b[i]), s.push_back(c[i]);
    sort(s.begin(), s.end());
    s.resize(unique(s.begin(), s.end()) - s.begin());
    n = s.size();
    for (ll i = 0; i < m; i++)
        a[i] = lower_bound(s.begin(), s.end(), a[i]) - s.begin(),
        b[i] = lower_bound(s.begin(), s.end(), b[i]) - s.begin(),
        c[i] = lower_bound(s.begin(), s.end(), c[i]) - s.begin();

    iota(p, p + m, 0);
    ST tl(n);
    tl.update(0, 0);
    ST tr(n);
    tr.update(n - 1, 0);
    ll ans = 1e18;
    for (ll i = 0; i < m; i++) {
        ans = min(ans, tl.get(a[p[i]], n) + tr.get(0, b[p[i]] + 1) + d[p[i]]);
        tl.update(c[p[i]], tl.get(a[p[i]], n) + d[p[i]]);
        tr.update(c[p[i]], tr.get(0, b[p[i]] + 1) + d[p[i]]);
    }
    cout << (ans == 1e18 ? -1 : ans);
}

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