记录编号	292619	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2016]区间	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	9.348 s
提交时间	2016-08-09 10:53:35	内存使用	44.92 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define mid ((l+r)>>1)
using namespace std;
const int maxn=1000010;
const int INF=1000000000;
int Mx[maxn<<2],sum[maxn<<2],ans=INF,n,m,N;
int la[maxn],lb[maxn],b[maxn],p[maxn],kl[maxn];
bool cmp(int a,int b){return kl[a]<kl[b];}
void Modify(int x,int l,int r,int a,int b,int v){
	if(l>=a&&r<=b){Mx[x]+=v;sum[x]+=v;return;}
	if(mid>=a)Modify(x<<1,l,mid,a,b,v);
	if(mid<b)Modify(x<<1|1,mid+1,r,a,b,v);
	Mx[x]=max(Mx[x<<1],Mx[x<<1|1])+sum[x];
}
int main(){
	freopen("interval.in","r",stdin);
	freopen("interval.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;p[i]=i,i++){
		scanf("%d%d",&la[i],&lb[i]);
		b[++N]=la[i];b[++N]=lb[i];
		kl[i]=lb[i]-la[i]+1;
	}	
	sort(p+1,p+n+1,cmp);sort(b+1,b+N+1);
	N=unique(b+1,b+N+1)-b-1;
	for(int t=1;t<=n;t++){int i=p[t];
		la[i]=lower_bound(b+1,b+N+1,la[i])-b;
		lb[i]=lower_bound(b+1,b+N+1,lb[i])-b;
	}
	for(int i=1,j=0;j<n||Mx[1]==m&&j==n;){
		while(Mx[1]<m&&j<n)++j,Modify(1,1,N,la[p[j]],lb[p[j]],1);
		while(Mx[1]==m&&i<=n)ans=min(ans,kl[p[j]]-kl[p[i]]),Modify(1,1,N,la[p[i]],lb[p[i]],-1),i++;
	}
	if(ans==INF)ans=-1;
	printf("%d\n",ans);
	return 0;
}