Submission #314105

#	Time	Username	Problem	Language	Result	Execution time	Memory
314105		apostoldaniel854	Pinball (JOI14_pinball)	C++14	100 / 100	678 ms	38776 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct SegMin {
    vector <ll> seg;
    int n;
    SegMin (int _n) {
        n = _n;
        seg.resize (n * 4 + 4, (1ll << 60));
    }
    void updatePos (int node, int lb, int rb, int pos, ll val) {
        if (lb == rb) {
            seg[node] = min (seg[node], val);
            return;
        }
        int mid = (lb + rb) / 2;
        if (pos <= mid)
            updatePos (node * 2, lb, mid, pos, val);
        else
            updatePos (node * 2 + 1, mid + 1, rb, pos, val);
        seg[node] = min (seg[node * 2], seg[node * 2 + 1]);
    }
    ll queryRange (int node, int lb, int rb, int lQ, int rQ) {
        if (lQ <= lb && rb <= rQ)
            return seg[node];
        int mid = (lb + rb) / 2;
        ll ans = (1ll << 60);
        if (mid >= lQ)
            ans = min (ans, queryRange (node * 2, lb, mid, lQ, rQ));
        if (mid < rQ)
            ans = min (ans, queryRange (node * 2 + 1, mid + 1, rb, lQ, rQ));
        return ans;
    }
};
const int N = 1e5;
int a[1 + N], b[1 + N], c[1 + N], d[1 + N];

#define dbg(x) cerr << #x << " " << x << "\n"

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    int m, n;
    cin >> m >> n;
    map <int, int> mp;
    mp[1]; mp[n];
    for (int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        mp[a[i]]; mp[b[i]]; mp[c[i]];
    }
    int nr = 0;
    for (auto &x : mp)
        x.second = ++nr;
    for (int i = 1; i <= m; i++) {
        a[i] = mp[a[i]]; b[i] = mp[b[i]]; c[i] = mp[c[i]];
    }

    SegMin pref (nr), suff (nr);
    pref.updatePos (1, 1, nr, 1, 0);
    suff.updatePos (1, 1, nr, nr, 0);
   /// dbg (nr);
    ll ans = (1ll << 60);
    for (int i = 1; i <= m; i++) {
       /// dbg (i);
       /// dbg (a[i]); dbg (b[i]); dbg (c[i]);
        ll bestL = pref.queryRange (1, 1, nr, a[i], b[i]);
        ll bestR = suff.queryRange (1, 1, nr, a[i], b[i]);
        ans = min (ans, bestL + bestR + d[i]);
        pref.updatePos (1, 1, nr, c[i], bestL + d[i]);
        suff.updatePos (1, 1, nr, c[i], bestR + d[i]);
    }
    if (ans == (1ll << 60))
        ans = -1;
    cout << ans << "\n";
    return 0;
}

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