Submission #1169953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169953		Sharky	Treatment Project (JOI20_treatment)	C++20	35 / 100	8 ms	1352 KiB

treatment

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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define int long long
#define fi first
#define se second

#define L(i, j, k) for (int i = (j); i <= (k); i++)
#define R(i, j, k) for (int i = (j); i >= (k); i--)
#define all(x) x.begin(), x.end()

const int N = 5005;
const int inf = 1e18;

struct Treatment {
    int t, l, r, c;
} arr[N];

int di[N];
vector<pair<int, int>> adj[2 * N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

void ae(int u, int v, int w) {
    // cout << "addedge: " << u << " " << v << " " << w << '\n';
    adj[u].push_back({v, w});
}

queue<int> q;

struct SegTree {
    int size = 1;
    vector<int> seg;
    void init(int sz) {
        int size = 1;
        while (size < sz) size *= 2;
        seg.assign(2 * size + 10, inf);
    }
    void update(int source, int k, int ql, int qr, int l, int r, int id) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr && seg[id] > k) return;
        if (l == r) {
            di[l] = min(di[l], di[source] + arr[l].c);
            pq.push({di[l], l});
            seg[id] = inf;
            return;
        }
        int mid = (l + r) / 2;
        update(source, k, ql, qr, l, mid, id * 2);
        update(source, k, ql, qr, mid + 1, r, id * 2 + 1);
        seg[id] = min(seg[id * 2], seg[id * 2 + 1]);
    }
    void force_update(int pos, int val, int l, int r, int id) {
        if (l == r) {
            seg[id] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) force_update(pos, val, l, mid, id * 2);
        else force_update(pos, val, mid + 1, r, id * 2 + 1);
        seg[id] = min(seg[id * 2], seg[id * 2 + 1]);
    }
} ST1, ST2;

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> arr[i].t >> arr[i].l >> arr[i].r >> arr[i].c;
        di[i] = inf;
    }
    sort(arr + 1, arr + m + 1, [] (auto x, auto y) { return x.t < y.t; });
    ST1.init(m + 1); ST2.init(m + 1);
    for (int i = 1; i <= m; i++) {
        ST1.force_update(i, arr[i].l + arr[i].t, 1, m, 1);
        ST2.force_update(i, arr[i].l - arr[i].t, 1, m, 1);
        // cout << arr[i].t << " " << arr[i].l << " " << arr[i].r << " " << arr[i].c << '\n';
    }
    di[0] = 0;
    for (int i = 1; i <= m; i++) {
        if (arr[i].l == 1) {
            di[i] = arr[i].c;
            pq.push({di[i], i});
            ST1.force_update(i, inf, 1, m, 1);
            ST2.force_update(i, inf, 1, m, 1);
        }
    }
    while (!pq.empty()) {
        auto [dist, i] = pq.top();
        pq.pop();
        if (dist != di[i]) continue;
        // cout << "pq " << dist << " " << i << '\n';
        ST1.update(i, arr[i].r + 1 + arr[i].t, i + 1, m, 1, m, 1);
        ST2.update(i, arr[i].r + 1 - arr[i].t, 1, i - 1, 1, m, 1);
    }
    int ans = inf;
    for (int i = 1; i <= m; i++) if (arr[i].r == n) ans = min(ans, di[i]);
    if (ans == inf) cout << "-1\n";
    else cout << ans << '\n';
    // sort projects, then point to interval edges
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int test = 1;
    // cin >> test;
    while (test--) solve();
}

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