记录编号	600203	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2016]区间	最终得分	100
用户昵称	长安惊龙灵松	是否通过	通过
代码语言	C++	运行时间	3.035 s
提交时间	2025-04-19 17:19:59	内存使用	7.89 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=9e5+5; 
int n,m,p[N<<1],lazy[N<<2],ma[N<<2],ans=0x7fffffff;
struct node{int l,r;}a[N];
int cmp(node x,node y){return x.r-x.l<y.r-y.l;}
int sum(int l,int r){return p[a[r].r]-p[a[r].l]-p[a[l].r]+p[a[l].l];}
void add(int k,int l,int r,int x,int y,int z)
{
    if(l>=x&&r<=y)
    {
        lazy[k]+=z,ma[k]+=z;
        return;
    }
    int mid=l+((r-l)>>1);
    if(x<=mid) add(k<<1,l,mid,x,y,z);
    if(y>mid)  add(k<<1|1,mid+1,r,x,y,z);
    ma[k]=max(ma[k<<1],ma[k<<1|1])+lazy[k];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r),p[2*i-1]=a[i].l,p[2*i]=a[i].r;
    int nn=2*n;sort(p+1,p+nn+1);nn=unique(p+1,p+nn+1)-p-1;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        a[i].l=lower_bound(p+1,p+nn+1,a[i].l)-p;
        a[i].r=lower_bound(p+1,p+nn+1,a[i].r)-p;
    }
    for(int l=1,r=0;l<=n;add(1,1,nn,a[l].l,a[l].r,-1),l++)
    {
        while(r<n&&ma[1]<m)
            r++,add(1,1,nn,a[r].l,a[r].r,1);
        if(r==n&&ma[1]<m) break;
        ans=min(ans,sum(l,r));
    }
    printf("%d",ans==0x7fffffff?-1:ans);
    return 0;
}