记录编号	586374	评测结果	AAAAAAAAAAAAAA
题目名称	[USACO Dec04]清理牛棚	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.064 s
提交时间	2024-01-17 20:11:39	内存使用	20.18 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10,M = N<<2,inf = 1e8;
int n,m;
struct made{
    int l,r;
    bool operator < (made x)const{
        return r < x.r;
    }
}a[N];
int f[N];
struct segment_tree{
    int mi[M];
    void update(int p){
        mi[p] = min(mi[p<<1],mi[p<<1|1]);
    }
    void build(int p,int l,int r){
        mi[p] = inf;
        if(l == r)return;
        int mid = l + r >> 1;
        build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    }
    void modify(int p,int l,int r,int L,int z){
        if(l == r){mi[p] = z;return;}
        int mid = l + r >> 1;
        if(L <= mid)modify(p<<1,l,mid,L,z);
        else modify(p<<1|1,mid+1,r,L,z);
        update(p);
    }
    int ask(int p,int l,int r,int L,int R){
        if(L <= l && r <= R)return mi[p];
        int mid = l + r >> 1;
        if(R <= mid)return ask(p<<1,l,mid,L,R);
        else if(L > mid)return ask(p<<1|1,mid+1,r,L,R);
        else return min(ask(p<<1,l,mid,L,R),ask(p<<1|1,mid+1,r,L,R));
    }
}T;
int main(){
    freopen("cleanshifts.in","r",stdin);
    freopen("cleanshifts.out","w",stdout);
    scanf("%d%d",&m,&n);
    for(int i = 1;i <= m;i++)scanf("%d%d",&a[i].l,&a[i].r);
    sort(a+1,a+1+m);
    T.build(1,0,n);
    T.modify(1,0,n,0,0);
    for(int i = 1;i <= n;i++)f[i] = inf;
    for(int i = 1;i <= m;i++){
        int l = a[i].l,r = a[i].r;
        f[r] = min(f[r],T.ask(1,0,n,l-1,r-1)+1);
        T.modify(1,0,n,r,f[r]);
    }
    if(f[n] == inf)printf("-1\n");
    else printf("%d\n",f[n]);
    
    return 0;
    
}