Submission #391560

#	Time	Username	Problem	Language	Result	Execution time	Memory
391560		KoD	Pinball (JOI14_pinball)	C++17	100 / 100	162 ms	12420 KiB

pinball

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

using ll = long long;

constexpr ll INF = std::numeric_limits<ll>::max() / 3;

struct Segtree {
    int size;
    Vec<ll> min;
    Segtree(const int n): size(n), min(2 * n, INF) { }

    void setmin(int i, const ll x) {
        i += size;
        while (i > 0) {
            min[i] = std::min(min[i], x);
            i >>= 1;
        }
    }

    ll fold(int l, int r) const {
        ll ret = INF;
        l += size;
        r += size;
        while (l < r) {
            if (l & 1) ret = std::min(ret, min[l++]);
            if (r & 1) ret = std::min(ret, min[--r]);
            l >>= 1;
            r >>= 1;
        }
        return ret;
    }
};

int read() {
    char c = getchar_unlocked();
    while (c < '0' or c > '9') {
        c = getchar_unlocked();
    }
    int x = 0;
    while ('0' <= c and c <= '9') {
        x *= 10;
        x += c - '0';
        c = getchar_unlocked();
    }
    return x;
}

int main() {
    int H = read();
    int W = read();
    Vec<int> A(H), B(H), C(H), D(H);
    Vec<int> cmp;
    cmp.reserve(3 * H + 2);
    cmp.push_back(1);
    cmp.push_back(W);
    for (int i = 0; i < H; ++i) {
        A[i] = read();
        B[i] = read();
        C[i] = read();
        D[i] = read();
        cmp.push_back(A[i]);
        cmp.push_back(B[i]);
        cmp.push_back(C[i]);
    }
    std::sort(cmp.begin(), cmp.end());
    cmp.erase(std::unique(cmp.begin(), cmp.end()), cmp.end());
    for (auto& x: A) {
        x = std::lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
    }
    for (auto& x: B) {
        x = std::lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
    }
    for (auto& x: C) {
        x = std::lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
    }
    W = (int) cmp.size();
    Segtree left(W), right(W);
    left.setmin(0, 0);
    right.setmin(W - 1, 0);
    ll ans = INF;
    for (int i = 0; i < H; ++i) {
        left.setmin(C[i], left.fold(A[i], C[i]) + D[i]);
        right.setmin(C[i], right.fold(C[i] + 1, B[i] + 1) + D[i]);
        ans = std::min(ans, left.fold(A[i], W) + right.fold(0, B[i] + 1) + D[i]);
    }
    if (ans == INF) {
        std::cout << -1 << '\n';
    }
    else {
        std::cout << ans << '\n';
    }
    return 0;
}

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