Submission #601330

#	Time	Username	Problem	Language	Result	Execution time	Memory
601330		elkernos	Pinball (JOI14_pinball)	C++17	100 / 100	184 ms	16460 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

struct tree {
    typedef long long T;
    T f(T a, T b) { return min(a, b); }
    vector<T> s;
    int n;
    T unit = 0;
    tree(int nn, T fil) : s(2 * nn, fil), n(nn), unit(fil) {}
    void update(int p, T v)
    {
        p += n;
        for(s[p] = min(s[p], v); p /= 2;) {
            s[p] = f(s[2 * p], s[2 * p + 1]);
        }
    }
    T query(int a, int b)
    {
        T ra = unit, rb = unit;
        for(a += n, b += n + 1; a < b; a /= 2, b /= 2) {
            if(a % 2) ra = f(ra, s[a++]);
            if(b % 2) rb = f(rb, s[--b]);
        }
        return f(ra, rb);
    }
};

#define make_unique(v) sort((v).begin(), (v).end()), (v).erase(unique((v).begin(), (v).end()), (v).end())

struct scaler {
    vector<int> all;
    void insert(int x) { all.emplace_back(x); }
    void init() { make_unique(all); }
    int get(int x) { return lower_bound(all.begin(), all.end(), x) - all.begin(); }
};

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int m, n;
    cin >> m >> n;
    scaler s;
    vector<int> a(m + 1), b(m + 1), c(m + 1), d(m + 1);
    for(int i = 1; i <= m; ++i) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        s.insert(a[i]), s.insert(b[i]), s.insert(c[i]);
    }
    s.insert(1), s.insert(n);
    s.init();
    for(int i = 1; i <= m; ++i) {
        a[i] = s.get(a[i]), b[i] = s.get(b[i]), c[i] = s.get(c[i]);
    }
    int sz = (int)s.all.size();
    const long long oo = 1e18 + 5;
    tree one(sz + 123, oo), two(sz + 123, oo);
    one.update(s.get(0), 0);
    two.update(s.get(n), 0);
    long long ans = oo;
    for(int i = 1; i <= m; ++i) {
        long long dp1 = one.query(a[i], b[i]);
        one.update(c[i], dp1 + d[i]);
        long long dp2 = two.query(a[i], b[i]);
        two.update(c[i], dp2 + d[i]);
        ans = min(ans, dp1 + dp2 + d[i]);
    }
    cout << (ans == oo ? -1 : ans) << '\n';
}

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