C++14(g++5.4) 解法, 执行用时: 1498ms, 内存消耗: 43000K, 提交时间: 2019-07-10 10:43:58

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
struct node
{
	int l,r,len;
}q[maxn];
struct node1
{
	int l,r,f,sum;
}tr[maxn*6];
int n,m,x,y,val;
bool cmp(node a,node b){
	return a.len<b.len;
}
void down(int k){
	tr[2*k].sum+=tr[k].f;
	tr[2*k+1].sum+=tr[k].f;
	tr[2*k].f+=tr[k].f;
	tr[2*k+1].f+=tr[k].f;
	tr[k].f=0;
}
void creat(int l,int r,int k)
{
	tr[k].l=l;tr[k].r=r;tr[k].f=0;tr[k].sum=0;
	if(l==r)	return;
	int mid=(l+r)/2;
	creat(l,mid,2*k);
	creat(mid+1,r,2*k+1);
}
void updata(int k){
	if(tr[k].l>=x&&tr[k].r<=y){
		tr[k].sum+=val;
		tr[k].f+=val;
		return;
	}
	down(k);
	int mid=(tr[k].l+tr[k].r)/2;
	if(mid>=x)	updata(2*k);
	if(mid<y)	updata(2*k+1);
	tr[k].sum=max(tr[2*k].sum,tr[2*k+1].sum);
}
int a[2*maxn];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&x,&y);
		q[i].l=x;
		q[i].r=y;
		q[i].len=y-x;
		a[++a[0]]=x;
		a[++a[0]]=y;
	}
	sort(a+1,a+a[0]+1);
	a[0]=unique(a+1,a+a[0]+1)-(a+1);
	for(int i=1;i<=n;i++){
		q[i].l=lower_bound(a+1,a+1+a[0],q[i].l)-(a);
		q[i].r=lower_bound(a+1,a+1+a[0],q[i].r)-(a);
	}
	sort(q+1,q+1+n,cmp);int t=0,inf=1<<30,ans=inf;
	creat(1,a[0],1);
	for(int i=1;i<=n;i++){
		while(t<n&&tr[1].sum<m)	
			t++,x=q[t].l,y=q[t].r,val=1,updata(1);
		if(tr[1].sum>=m)	ans=min(ans,q[t].len-q[i].len);
		else	break;
		x=q[i].l;y=q[i].r;val=-1;
		updata(1);
	}
	if(ans!=inf)	printf("%d",ans);
	else	printf("-1");
}

C++11(clang++ 3.9) 解法, 执行用时: 1584ms, 内存消耗: 24680K, 提交时间: 2019-01-07 18:43:55

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int l,r;
}a[500001];
struct tree
{
    int plus,sum;
}t[4000001];
int s[1000001];
int n,m,tot,L=1,R,ans=0x7fffffff;
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
inline bool cmp(node a,node b)
{
    return (a.r-a.l)<(b.r-b.l);
}
void add(int L,int R,int l,int r,int now,int num)
{
    if(L<=l&&r<=R)
    {
        t[now].plus+=num,t[now].sum+=num;
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid) add(L,R,l,mid,now<<1,num);
    if(R>mid) add(L,R,mid+1,r,now<<1|1,num);
    t[now].sum=max(t[now<<1].sum,t[now<<1|1].sum)+t[now].plus;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].l,&a[i].r);
        s[++tot]=a[i].l;
        s[++tot]=a[i].r;
    }
    sort(s+1,s+tot+1);
    tot=unique(s+1,s+tot+1)-s-1;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        a[i].l=lower_bound(s+1,s+tot+1,a[i].l)-s;
        a[i].r=lower_bound(s+1,s+tot+1,a[i].r)-s;
    }
    while(L<=n)
    {
        while(R<n&&t[1].sum<m) R++,add(a[R].l,a[R].r,1,tot,1,1);
        if(t[1].sum>=m) ans=min(ans,s[a[R].r]-s[a[R].l]-s[a[L].r]+s[a[L].l]);
        add(a[L].l,a[L].r,1,tot,1,-1),L++;
    }
    if(ans==0x7fffffff) printf("-1");
    else printf("%d",ans);
    return 0;
}