记录编号	356853	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2016]区间	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	6.715 s
提交时间	2016-12-06 20:43:34	内存使用	91.84 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=4000010,maxl=1000000001;
struct qj{int l,r,len;}q[N];
bool cmp(const qj &x,const qj &y){
	return x.len<y.len;
}
int n,m,a[N],cnt;
int find(int x,int l,int r){
	if (l==r) return l;
	int mid=(l+r)/2;
	return a[mid]>=x?find(x,l,mid):find(x,mid+1,r);
}
int tag[N],Max[N];
#define lc x<<1
#define rc (x<<1)|1
void pushdown(int x,int l,int r){
	if (tag[x]&&l!=r){
		tag[lc]+=tag[x];Max[lc]+=tag[x];
		tag[rc]+=tag[x];Max[rc]+=tag[x];
		tag[x]=0;
	}
}
void add(int x,int l,int r,int L,int R,int d){
	pushdown(x,l,r);
	if (l>=L&&r<=R){
		tag[x]+=d;Max[x]+=d;
		return;
	}
	int mid=(l+r)>>1;
	if (R>mid) add(rc,mid+1,r,L,R,d);
	if (L<=mid) add(lc,l,mid,L,R,d);
	Max[x]=max(Max[lc],Max[rc]);
}
inline int read(){
	char ch=getchar();int _x=0;
	while (ch>'9'||ch<'0') ch=getchar();
	while (ch<='9'&&ch>='0') _x=_x*10+ch-48,ch=getchar();
	return _x;
}
int main()
{
	freopen("interval.in","r",stdin);
	freopen("interval.out","w",stdout);
	n=read();m=read();
	for (int i=1;i<=n;i++){
		q[i].l=read();q[i].r=read();
		q[i].len=q[i].r-q[i].l;
		a[++cnt]=q[i].l;
		a[++cnt]=q[i].r;
	}
	sort(q+1,q+n+1,cmp);
	sort(a+1,a+cnt+1);
	for (int i=1;i<=n;i++)
		q[i].l=find(q[i].l,1,cnt),q[i].r=find(q[i].r,1,cnt);
	int mi=q[1].len,ma,ans=maxl,del=1;
	for (int i=1;i<=n;i++){
		add(1,1,n*2,q[i].l,q[i].r,1);
		ma=q[i].len;
		while (Max[1]>=m){
			ans=min(ans,ma-mi);
			add(1,1,n*2,q[del].l,q[del].r,-1);
			mi=q[++del].len;
		}
	}
	printf("%d\n",ans==maxl?-1:ans);
	return 0;
}