Submission #825102

#	Time	Username	Problem	Language	Result	Execution time	Memory
825102		Koyote	Pinball (JOI14_pinball)	C++14	11 / 100	2 ms	596 KiB

pinball

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

template<typename S, S (*op)(S, S), S (*e)()> struct dynamic_segtree {
  public:
    dynamic_segtree() : left(nullptr), right(nullptr) {}
    dynamic_segtree(int64_t _lt, int64_t _rt, S _val = e()) :
        lt_idx(_lt), rt_idx(_rt), mid_idx((_lt + _rt) >> 1), val(_val) {
            if (_lt != _rt) {
                left = new dynamic_segtree<S, op, e>(_lt, mid_idx);
                right = new dynamic_segtree<S, op, e>(mid_idx + 1, _rt);
            }
        }
    void update(int64_t p, S new_val) {
        if (lt_idx == rt_idx) return void(val = op(val, new_val));
        if (p <= mid_idx) left->update(p, new_val);
        else right->update(p, new_val);
        val = op(left->val, right->val);
    }
    S prod(int64_t ql, int64_t qr) {
        if (qr < lt_idx || rt_idx < ql) return e();
        if (ql <= lt_idx && rt_idx <= qr) return val;
        auto left_val = left->prod(ql, qr);
        auto right_val = right->prod(ql, qr);
        return op(left_val, right_val);
    }
  private:
    dynamic_segtree<S, op, e> *left, *right;
    int64_t lt_idx, rt_idx, mid_idx;
    S val;
};

int64_t op(int64_t a, int64_t b) { return min(a, b); }
int64_t e() { return int64_t(1e18); }

const int N = 1e5 + 2;
int m, n, a[N], b[N], c[N], d[N];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 0; i < m; i++) cin >> a[i] >> b[i] >> c[i] >> d[i];

    vector<int> compr({1, n}); compr.reserve(n * 3 + 2);
    for (int i = 0; i < m; i++)
        compr.push_back(a[i]), compr.push_back(b[i]), compr.push_back(c[i]);
    sort(compr.begin(), compr.end());
    compr.erase(unique(compr.begin(), compr.end()), compr.end());
    auto get_compress_value = [&compr](int x) {
        return lower_bound(compr.begin(), compr.end(), x) - compr.begin() + 1;
    };
    n = get_compress_value(n);
    for (int i = 0; i < m; i++) {
        a[i] = get_compress_value(a[i]);
        b[i] = get_compress_value(b[i]);
        c[i] = get_compress_value(c[i]);
    }

    auto *Ltree = new dynamic_segtree<int64_t, op, e>(1, n);
    auto *Rtree = new dynamic_segtree<int64_t, op, e>(1, n);
    Ltree->update(1, 0), Rtree->update(n, 0);
    
    int64_t ans = e();
    for (int i = 0; i < m; i++) {
        auto min_val_left = Ltree->prod(a[i], b[i]);
        auto min_val_right = Rtree->prod(a[i], b[i]);
        ans = min(ans, min_val_left + min_val_right + d[i]);
        Ltree->update(c[i], d[i] + min_val_left);
        Rtree->update(c[i], d[i] + min_val_right);
    }
    cout << (ans == e() ? -1 : ans) << '\n';
}

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