Submission #106261

#	Time	Username	Problem	Language	Result	Execution time	Memory
106261		popovicirobert	Pinball (JOI14_pinball)	C++14	51 / 100	1067 ms	2716 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 {

    struct Node {
        Node *st, *dr;
        ll mn;
        Node() {
            st = dr = NULL;
            mn = INF;
        }
    };

    Node *root;

    inline void init() {
        root = new Node;
    }

    void update(Node *nod, int left, int right, int pos, ll val) {
        nod -> mn = min(nod -> mn, val);
        if(left < right) {
            int mid = (left + right) / 2;
            if(pos <= mid) {
                if(nod -> st == NULL) {
                    nod -> st = new Node;
                }
                update(nod -> st, left, mid, pos, val);
            }
            else {
                if(nod -> dr == NULL) {
                    nod -> dr = new Node;
                }
                update(nod -> dr, mid + 1, right, pos, val);
            }
        }
    }

    void update(int left, int right, int pos, ll val) {
        update(root, left, right, pos, val);
    }

    ll query(Node *nod, int left, int right, int l, int r) {
        if(nod == NULL) {
            return INF;
        }
        if(l <= left && right <= r) {
            return nod -> mn;
        }
        else {
            int mid = (left + right) / 2;
            ll ans = INF;
            ans = min(query(nod -> st, left, mid, l, r), query(nod -> dr, mid + 1, right, l, r));
            return ans;
        }
    }

    ll query(int left, int right, int l, int r) {
        return query(root, left, right, l, r);
    }

};

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;

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

    vector < vector <ll> > dp(m + 1, vector<ll>(4, INF));
    for(i = 1; i <= m; i++) {
        int l, r, pos;
        ll cst;
        cin >> l >> r >> pos >> cst;

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

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

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

        for(int j = 1; j <= 2; j++) {
            st[j].update(1, n, pos, 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: 0 / 49