Submission #581580

#	Time	Username	Problem	Language	Result	Execution time	Memory
581580		Vanilla	Pinball (JOI14_pinball)	C++17	0 / 100	14 ms	25300 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 1e5 + 2;
int64 a[maxn], b[maxn], c[maxn], cost[maxn];
vector <int64> coord;
int64 n,m;

template <class T> class segtree {

    private:
        vector <T> tree;
        int n, il, ir;
        
        void build (vector <T> &a, int node, int l, int r) {
            if (l == r) {
                tree[node] = a[l];
                return;
            }
            int m = (l + r) / 2;
            build(a, node * 2, l, m);
            build(a, node * 2 + 1, m + 1, r);
            tree[node] = calc(tree[node * 2], tree[node * 2 + 1]);
        }
        
        T __query (int node, int l, int r) {
            if (il <= l && r <= ir) return tree[node];
            T s1 = 1e15, s2 = 1e15;
            int m = (l + r) / 2;
            if (il <= m) {
                s1 = __query(node * 2, l, m);
            }
            if (m + 1 <= ir) {
                s2 = __query(node * 2 + 1, m + 1, r);
            }
            return calc(s1, s2);
        }

        void __update (int node, int l, int r, int& px, T& val) {
            if (l == r) {
                tree[node] = val;
                return;
            }
            int m = (l + r) / 2;
            if (px <= m) {
                __update(node * 2, l, m, px, val);
            }
            else {
                __update(node * 2 + 1, m + 1, r, px, val);
            }
            tree[node] = calc(tree[node * 2], tree[node * 2 + 1]);
        }

    public: 
        segtree (int n) {
            this->n = n;
            tree.resize(n * 4);
            for (int i = 0; i < n * 4; i++){
                tree[i] = 1e15;
            }
        }

        T query (int l, int r) {
            il = l, ir = r;
            return __query(1, 0, n);
        }

        void update (int pos, T val) {
            return __update(1, 0, n, pos, val);
        }

        T calc (T a, T b) {
            return min(a, b);
        }

};

segtree <int64> mnl (maxn * 4);
segtree <int64> mnr (maxn * 4);
 
 
int main() {
    cin >> n >> m;
    bool f1 = 0, f2 = 0;
    for (int i = 0; i < n; i++){
        cin >> a[i] >> b[i] >> c[i] >> cost[i];
        if (a[i] == 1) f1 = 1;
        if (b[i] == m) f2 = 1;
        coord.push_back(a[i]);
        coord.push_back(b[i]);
        coord.push_back(c[i]);
    }
    if (!f1 || !f2){
        cout << -1;
        return 0;
    }
    sort(coord.begin(), coord.end());
    coord.erase(unique(coord.begin(), coord.end()), coord.end());
    m = 0;
    for (int i = 0; i < n; i++){
        a[i] = lower_bound(coord.begin(), coord.end(), a[i]) - coord.begin();
        b[i] = lower_bound(coord.begin(), coord.end(), b[i]) - coord.begin();
        c[i] = lower_bound(coord.begin(), coord.end(), c[i]) - coord.begin();
        m = max(m, b[i]);
    }
    int64 rs = 1e15;
    mnl.update(0, 0);
    mnr.update(m, 0);
    for (int i = 0; i < n; i++){
        rs = min(rs, mnl.query(a[i], b[i]) + mnr.query(a[i], b[i]) + cost[i]);
        mnl.update(c[i], mnl.query(a[i], b[i]) + cost[i]);
        mnr.update(c[i], mnr.query(a[i], b[i]) + cost[i]);
    }
 
    cout << (rs >= 1e15 ? -1: rs);
}

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