Submission #371165

#	Time	Username	Problem	Language	Result	Execution time	Memory
371165		12tqian	Treatment Project (JOI20_treatment)	C++17	0 / 100	61 ms	10468 KiB

treatment

#include <bits/stdc++.h>

using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int N = 1e5 + 5;
const int L = 20;
const ll INF = 1e18;

int n, m, t[N], l[N], r[N], c[N], a[N], pos[N];

vpl v;

struct Node {
    ll val;
    int v;
    Node() {}
    Node(ll val, int v) : val(val), v(v) {}
    Node operator + (const Node& A) { // set min
        if (val <= A.val) return *this;
        return A;
    }
} st[(1 << L)];

void pull(int ind) {
    st[ind] = st[2 * ind] + st[2 * ind + 1];
}

void upd(Node A, int id, int ind = 1, int l = 0, int r = (1 << L) - 1) {
    if (id < l || id > r) return;
    if (l == r) { 
        st[ind] = A;
        return;
    }
    int m = (l + r) >> 1;
    upd(A, id, 2 * ind, l, m);
    upd(A, id, 2 * ind + 1, m + 1, r);
    pull(ind);
}

Node query(int lo, int hi, int ind = 1, int l = 0, int r = (1 << L) - 1) {
    if (r < lo || hi < l) return Node(INF, -1);
    if (lo <= l && r <= hi) return st[ind];
    int m = (l + r) >> 1;
    return query(lo, hi, 2 * ind, l, m) + query(lo, hi, 2 * ind + 1, m + 1, r);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> m >> n;
    f0r(i, n) {
        cin >> t[i] >> l[i] >> r[i] >> c[i];
        l[i]--;
        v.eb(l[i] + t[i], i);
    }
    sort(all(v));
    f0r(i, n) {
        int id = v[i].s;
        a[i] = l[id] - t[id];
        pos[id] = i;
        upd(Node(a[i], id), i);
    }
    priority_queue<pl> pq;
    f0r(i, n) {
        if (l[i] == 0) {
            pq.emplace(-c[i], i); // src nodes
            upd(Node(INF, i), pos[i]);
        }
    }
    ll ans = INF;
    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        int i = cur.s;
        ll w = cur.f;
        if (r[i] == m) { // reached end
            ckmin(ans, -w);
        }
        int y = upper_bound(all(v), mp((ll)r[i] + t[i], (ll)m - 1)) - v.begin() - 1;
        while (true) {
            Node x = query(0, y);
            if (x.val <= r[i] - t[i]) {
                pq.emplace(w - c[x.v], x.v);
                upd(Node(INF, -1), pos[x.v]);
            } else break;
        }
    }
    if (ans == INF) cout << -1 << '\n';
    else cout << ans << '\n';
    return 0;
}

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