Submission #106263

#	Time	Username	Problem	Language	Result	Execution time	Memory
106263		popovicirobert	Pinball (JOI14_pinball)	C++14	100 / 100	835 ms	47488 KiB

pinball

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const ll INF = 1e16;

struct SegTree {

    vector <ll> aint;
    int n;

    inline void init(int _n) {
        n = _n;
        aint.resize(4 * n + 1, INF);
    }

    void update(int nod, int left, int right, int pos, ll val) {
        aint[nod] = min(aint[nod], val);
        if(left < right) {
            int mid = (left + right) / 2;
            if(pos <= mid) update(2 * nod, left, mid, pos, val);
            else update(2 * nod + 1, mid + 1, right, pos, val);
        }
    }

    ll query(int nod, int left, int right, int l, int r) {
        if(l <= left && right <= r) {
            return aint[nod];
        }
        else {
            int mid = (left + right) / 2;
            ll ans = INF;
            if(l <= mid) ans = min(ans, query(2 * nod, left, mid, l, r));
            if(mid < r) ans = min(ans, query(2 * nod + 1, mid + 1, right, l, r));
            return ans;
        }
    }

};

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, m;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> m >> n;

    vector <int> l(m + 1), r(m + 1), pos(m + 1), nrm;
    vector <ll> cst(m + 1);

    for(i = 1; i <= m; i++) {
        cin >> l[i] >> r[i] >> pos[i] >> cst[i];
        nrm.push_back(l[i]);
        nrm.push_back(r[i]);
        nrm.push_back(pos[i]);
    }

    sort(nrm.begin(), nrm.end());
    nrm.resize(unique(nrm.begin(), nrm.end()) - nrm.begin());
    int sz = nrm.size();
    map <int, int> mp;

    for(i = 0; i < sz; i++) {
        mp[nrm[i]] = i + 1;
    }

    SegTree st[3];
    for(i = 1; i <= 2; i++) {
        st[i].init(sz);
    }

    vector < vector <ll> > dp(m + 1, vector<ll>(4, INF));

    for(i = 1; i <= m; i++) {

        if(l[i] == 1) {
            dp[i][1] = min(dp[i][1], cst[i]);
        }
        if(r[i] == n) {
            dp[i][2] = min(dp[i][2], cst[i]);
        }
        if(l[i] == 1 && r[i] == n) {
            dp[i][3] = min(dp[i][3], cst[i]);
        }

        l[i] = mp[l[i]], r[i] = mp[r[i]], pos[i] = mp[pos[i]];

        dp[i][1] = min(dp[i][1], cst[i] + st[1].query(1, 1, sz, l[i], r[i]));
        dp[i][2] = min(dp[i][2], cst[i] + st[2].query(1, 1, sz, l[i], r[i]));

        dp[i][3] = min(dp[i][3], cst[i] + st[1].query(1, 1, sz, l[i], r[i]) + st[2].query(1, 1, sz, l[i], r[i]));
        dp[i][3] = min(dp[i][3], dp[i][1] + dp[i][2] - cst[i]);

        for(int j = 1; j <= 2; j++) {
            st[j].update(1, 1, sz, pos[i], dp[i][j]);
        }
    }

    ll ans = INF;
    for(i = 1; i <= m; i++) {
        ans = min(ans, dp[i][3]);
    }
    if(ans == INF) {
        cout << -1;
        return 0;
    }
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}

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