oj.uz

Submission #898541

# Submission time Handle Problem Language Result Execution time Memory
898541 2024-01-04T21:08:45 Z box Treatment Project (JOI20_treatment) C++17
4 / 100
 239 ms 82732 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 54496 KB Output is correct
2 Correct 169 ms 57748 KB Output is correct
3 Correct 84 ms 15572 KB Output is correct
4 Correct 84 ms 15748 KB Output is correct
5 Correct 51 ms 10440 KB Output is correct
6 Correct 57 ms 10400 KB Output is correct
7 Correct 71 ms 14316 KB Output is correct
8 Correct 51 ms 10184 KB Output is correct
9 Correct 57 ms 9420 KB Output is correct
10 Correct 85 ms 14932 KB Output is correct
11 Correct 206 ms 64960 KB Output is correct
12 Correct 213 ms 64192 KB Output is correct
13 Correct 235 ms 80848 KB Output is correct
14 Correct 225 ms 80692 KB Output is correct
15 Correct 237 ms 82072 KB Output is correct
16 Correct 239 ms 82732 KB Output is correct
17 Correct 228 ms 80832 KB Output is correct
18 Correct 207 ms 63676 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 54496 KB Output is correct
2 Correct 169 ms 57748 KB Output is correct
3 Correct 84 ms 15572 KB Output is correct
4 Correct 84 ms 15748 KB Output is correct
5 Correct 51 ms 10440 KB Output is correct
6 Correct 57 ms 10400 KB Output is correct
7 Correct 71 ms 14316 KB Output is correct
8 Correct 51 ms 10184 KB Output is correct
9 Correct 57 ms 9420 KB Output is correct
10 Correct 85 ms 14932 KB Output is correct
11 Correct 206 ms 64960 KB Output is correct
12 Correct 213 ms 64192 KB Output is correct
13 Correct 235 ms 80848 KB Output is correct
14 Correct 225 ms 80692 KB Output is correct
15 Correct 237 ms 82072 KB Output is correct
16 Correct 239 ms 82732 KB Output is correct
17 Correct 228 ms 80832 KB Output is correct
18 Correct 207 ms 63676 KB Output is correct
19 Runtime error 1 ms 604 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -