清理班次

AcWing-295-清理班次

实现

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

const int N = 25010, M = 1000010;
struct interval {
    int l, r;
    bool operator < (const interval& o) const {
        return r < o.r;
    }
};
int n, m;
interval a[N];
struct node {
    int l, r;
    int 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, int 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);
}
int query (int rt, int l, int r) {
    if (l <= l(rt) && r(rt) <= r) return data(rt);
    int mid = l(rt) + r(rt) >> 1;
    int 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", &n, &m);
    for (int i = 1; i <= n; ++ i) scanf("%d%d", &a[i].l, &a[i].r);

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