Submission #1035089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035089		vjudge1	Pinball (JOI14_pinball)	C++17	100 / 100	171 ms	30164 KiB

pinball

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

using ll = long long;

#define fi first
#define se second
#define pb push_back
#define ep emplace_back
#define lwb lower_bound
#define upb upper_bound
#define gcd(x, y) __gcd(x, y)
#define lcm(x, y) x * y / __gcd(x, y)

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int mxN = 1e6 + 5;
const int block = 450;
const int base = 311;
const int LOG = 19;

struct pinball {
    ll a, b, c, d;
} a[mxN];

int m, n;

namespace sub3 {
    bool check() {
        return m <= 1000;
    }

    ll L[mxN], R[mxN];

    void solve() {
        for (int i = 1; i <= m; i++) {
            L[i] = inf;
            R[i] = inf;
        }
        for (int i = 1; i <= m; i++) {
            if (a[i].a == 1) {
                L[i] = a[i].d;
            }
            if (a[i].b == n) {
                R[i] = a[i].d;
            }
            for (int j = 1; j < i; j++) {
                if (a[j].a < a[i].a && a[i].a <= a[j].c && a[j].c <= a[i].b) {
                    L[i] = min(L[i], L[j] + a[i].d);
                }
                if (a[j].b > a[i].b && a[i].a <= a[j].c && a[j].c <= a[i].b) {
                    R[i] = min(R[i], R[j] + a[i].d);
                }
            }
        }
        ll ans = inf;
        for (int i = 1; i <= m; i++) {
            ans = min(ans, L[i] + R[i] - a[i].d);
        }
        if (ans == inf) {
            cout << -1;
        }
        else {
            cout << ans;
        }
    }
}

namespace sub4 {
    struct SegTree {
        int n;
        ll st[4 * mxN];

        void build() {
            for (int i = 1; i <= 4 * n; i++) {
                st[i] = inf;
            }
        }

        void update(int i, int l, int r, int p, ll val) {
            if (p < l || p > r) {
                return;
            }
            if (l == r) {
                st[i] = min(st[i], val);
                return;
            }
            int m = (l + r) / 2;
            update(i * 2, l, m, p, val);
            update(i * 2 + 1, m + 1, r, p, val);
            st[i] = min(st[i * 2], st[i * 2 + 1]);
        }

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

    ll p[mxN], q[mxN];
    vector<ll> v;

    void solve() {
        for (int i = 1; i <= m; i++) {
            v.pb(a[i].a);
            v.pb(a[i].b);
            v.pb(a[i].c);
        }
        v.pb(n);
        sort(v.begin(), v.end());
        v.resize(unique(v.begin(), v.end()) - v.begin());
        bool b = 0, c = 0;
        for (int i = 1; i <= m; i++) {
            if (a[i].a == 1) {
                b = 1;
                p[i] = a[i].d;
            }
            if (a[i].b == n) {
                c = 1;
                q[i] = a[i].d;
            }
            a[i].a = lwb(v.begin(), v.end(), a[i].a) - v.begin() + 1;
            a[i].b = lwb(v.begin(), v.end(), a[i].b) - v.begin() + 1;
            a[i].c = lwb(v.begin(), v.end(), a[i].c) - v.begin() + 1;
        }
        if (b + c < 2) {
            cout << -1;
            return;
        }
        n = v.size();
        L.n = n;
        R.n = n;
        L.build();
        R.build();
        for (int i = 1; i <= m; i++) {
            if (!p[i]) {
                p[i] = inf;
            }
            if (!q[i]) {
                q[i] = inf;
            }
        }
        for (int i = 1; i <= m; i++) {
            ll x = L.get(1, 1, n, a[i].a, a[i].b);
            ll y = R.get(1, 1, n, a[i].a, a[i].b);
            p[i] = min(p[i], x + a[i].d);
            q[i] = min(q[i], y + a[i].d);
            L.update(1, 1, n, a[i].c, p[i]);
            R.update(1, 1, n, a[i].c, q[i]);
        }
//        for (int i = 1; i <= m; i++) {
//            cout << p[i] << " ";
//        }
//        cout << '\n';
//        for (int i = 1; i <= m; i++) {
//            cout << p[i] << " ";
//        }
        ll ans = inf;
        for (int i = 1; i <= m; i++) {
//            cout << i << ": " << p[i] << " " << q[i] << '\n';
            ans = min(ans, p[i] + q[i] - a[i].d);
        }
        if (ans == inf) {
            cout << -1;
        }
        else {
            cout << ans;
        }
    }
}

int main() {
//    freopen("PINBALL.INP", "r", stdin);
//    freopen("PINBALL.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> m >> n;
    for (int i = 1; i <= m; i++) {
        cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d;
    }
    if (sub3::check()) return sub3::solve(), 0;
    sub4::solve();
}
/*
*/

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