清理班次2

AcWing-296-清理班次2

分析

见《进阶指南》第312页。

实现

#include <iostream>
#include <algorithm>
#define ls rt << 1
#define rs rt << 1 | 1
using namespace std;

typedef long long LL;
const int N = 10010, M = 90000;
const LL inf = 1e15;
struct interval {
    int l, r, w;
    bool operator < (const interval& o) const {
        return r < o.r;
    }
};
int n, m, e;
interval a[N];
struct node {
    int l, r;
    LL data;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define data(x) t[x].data
};
node t[M << 2];

void update (int rt) {
    data(rt) = min(data(ls), data(rs));
}
void build (int rt, int l, int r) {
    l(rt) = l, r(rt) = r;
    if (l == r) {
        data(rt) = inf;
        return;
    }
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    update(rt);
}
void modify (int rt, int idx, LL val) {
    if (l(rt) == r(rt)) {
        data(rt) = min(data(rt), val);
        return;
    }
    int mid = l(rt) + r(rt) >> 1;
    modify(idx <= mid ? ls : rs, idx, val);
    update(rt);
}
LL query (int rt, int l, int r) {
    if (l <= l(rt) && r(rt) <= r) return data(rt);
    int mid = l(rt) + r(rt) >> 1;
    LL res = inf;
    if (l <= mid) res = min(res, query(ls, l, r));
    if (r >= mid + 1) res = min(res, query(rs, l, r));
    return res;
}

int main () {
    scanf("%d%d%d", &n, &m, &e);
    for (int i = 1; i <= n; ++ i) scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].w);

    sort(a + 1, a + n + 1);
    build(1, m - 1, e);
    modify(1, m - 1, 0);
    for (int i = 1; i <= n; ++ i) {
        int l = a[i].l, r = a[i].r, w = a[i].w;
        LL val = query(1, l - 1, r - 1) + w; // f[r]
        modify(1, r, val);
    }
    LL res = query(1, e, e);
    printf("%lld", res == inf ? -1 : res);
    return 0;
}