Submission #898541

#	Time	Username	Problem	Language	Result	Execution time	Memory
898541		box	Treatment Project (JOI20_treatment)	C++17	4 / 100	239 ms	82732 KiB

treatment

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

#ifdef LOCAL
template <class T, class... U> void bug_h(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; }
#define bug(...) cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: ", bug_h(__VA_ARGS__)
#else
#define cerr if (0) cerr
#define bug(...)
#endif

#define ar array
#define all(v) std::begin(v), std::end(v)
#define sz(v) int(std::size(v))
typedef long long i64;
typedef vector<int> vi;
typedef pair<int, int> pi;

struct segt {
    int l, r;
    segt *lc = NULL, *rc = NULL;
    i64 x;
    segt(int l, int r) : l(l), r(r) {
        x = 1e18;
        if (l < r) {
            int m = (l + r) / 2;
            lc = new segt(l, m), rc = new segt(m + 1, r);
        }
    }
    void relax(int i, i64 y) {
        x = min(x, y);
        if (l < r) i <= lc->r ? lc->relax(i, y) : rc->relax(i, y);
    }
    i64 qry(int ql, int qr) {
        if (ql <= l && qr >= r) return x;
        if (qr <= lc->r) return lc->qry(ql, qr);
        if (ql >= rc->l) return rc->qry(ql, qr);
        return min(lc->qry(ql, qr), rc->qry(ql, qr));
    }
};

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int N, M;
    cin >> N >> M;
    vi T(M), L(M), R(M), C(M);
    vi x;
    auto f = [&](int i) {
        if (0 <= i && i <= N) x.push_back(i);
    };
    f(0), f(1), f(N);
    for (int i = 0; i < M; i++) {
        cin >> T[i] >> L[i] >> R[i] >> C[i];
        assert(T[i] == 1);
        for (int d : {-1, 0, 1}) f(L[i] + d), f(R[i] + d);
    }
    sort(all(x));
    x.erase(unique(all(x)), end(x));
    int X = sz(x);
    segt *root = new segt(0, X - 1);
    root->relax(0, 0);
    vector<vi> who(X);
    for (int i = 0; i < M; i++) {
        int p = lower_bound(all(x), L[i]) - begin(x);
        assert(p);
        who.at(p).push_back(i);
    }
    for (int i = 1; i < X; i++) {
        i64 v = root->qry(i - 1, X - 1);
        for (int h : who[i]) {
            int p = lower_bound(all(x), R[h]) - begin(x);
            root->relax(p, v + C[h]);
        }
    }
    i64 ans = root->qry(X - 1, X - 1);
    if (ans < i64(1e17)) cout << ans << '\n';
    else cout << "-1\n";
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 61