85pts求条awa

#include<bits/stdc++.h>
using namespace std;
const long long N=11451419;
long long n,m,lsh[N],ans=1e18+10;
struct node{
	long long l,r;
}a[N];
struct Node{
	long long l,r,mx,tag;
}t[1145141];
bool cmp(node x,node y)
{
	return x.r-x.l<y.r-y.l;
}
void pushdown(long long p)
{
	if(t[p].tag)
	{   
		t[p*2].mx+=t[p].tag; 
		t[p*2+1].mx+=t[p].tag; 
		t[p*2].tag+=t[p].tag;  
		t[p*2+1].tag+=t[p].tag;
		t[p].tag=0;
	}
}
void build(long long p,long long l,long long r)
{
	t[p].l=l;
	t[p].r=r;
	if(l==r)
	{
		t[p].mx=0;
		return;
	}
	long long mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}
void modify(long long p,long long l,long long r,long long v)
{
	//cout<<p<<"  "<<l<<" "<<r<<"\n";
	if(l<=t[p].l&&r>=t[p].r)
	{
		t[p].mx+=v;
		t[p].tag+=v;  
		return;
	}
	pushdown(p);
	long long mid=(t[p].l+t[p].r)/2;
	if(l<=mid)
	{
		modify(p*2,l,r,v);
	}
	if(r>mid)
	{
		modify(p*2+1,l,r,v);
	}
	t[p].mx=max(t[p*2].mx,t[p*2+1].mx);
	return;
}
long long query(long long l,long long r,long long p)
{
	//if(l==0&&r==0)return 0;
	if(l<=t[p].l&&r>=t[p].r)
	{
		return t[p].mx;
	}
	pushdown(p);
	long long mid=(t[p].l+t[p].r)/2,cnt=0;
	if(l<=mid)
	{
		cnt=max(cnt,query(l,r,p*2));
	}
	if(r>=mid+1)
	{
		cnt=max(cnt,query(l,r,p*2+1));
	}
	return cnt;
}
int main()
{
	//freopen("P1712_1.in","r",stdin);
	cin>>n>>m;
	for(long long i=1;i<=n;i++)
	{
		cin>>a[i].l>>a[i].r;
		lsh[(i-1)*2+1]=a[i].l,lsh[(i-1)*2+2]=a[i].r;
	}
	sort(a+1,a+1+n,cmp);
	sort(lsh+1,lsh+n*2+1);
	long long o=unique(lsh+1,lsh+1+n*2)-lsh-1;
	for(long long i=1;i<=n;i++)
	{
		a[i].l=lower_bound(lsh+1,lsh+o+1,a[i].l)-lsh;
		a[i].r=lower_bound(lsh+1,lsh+o+1,a[i].r)-lsh;
	}
	build(1,1,o);
	long long i=0,j=0;
	while(i<=o)
	{
		while(j<n&&query(1,o,1)<m)
		{
			modify(1,a[j+1].l,a[j+1].r,1);
			j++;
		}
		if(query(1,o,1)<m)break;
		while(i<=j&&query(1,o,1)>=m)
		{
			modify(1,a[i+1].l,a[i+1].r,-1);
			i++;
		}
		modify(1,a[i].l,a[i].r,1);
		if(query(0,o,1)==m)
		{
			ans=min(ans,lsh[a[j].r]-lsh[a[j].l]-(lsh[a[i].r]-lsh[a[i].l]));
		}
		modify(1,a[i].l,a[i].r,-1);
	}
	if(ans==1e18+10)
	{
		cout<<-1;
	}
	else
	{
		cout<<ans;
	}
	return 0;
}