传送门
解题思路
考虑尺取法。
将所有区间按照长度从小到大排序,然后tow-pointers在保证区间最大值>=m的情况下不断维护区间+1/-1。
用线段树维护。
AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
const int maxn=500005;
int a[maxn*2],cnt,n,m,ans=2e9,d[maxn*6],lazy[maxn*6];
struct node{
int l,r,len;
bool operator <(const node a)const{
return len<a.len;
}
}q[maxn];
inline void pushup(int id){
d[id]=max(d[id*2],d[id*2+1]);
}
inline void pushdown(int id){
if(lazy[id]){
lazy[id*2]+=lazy[id];
lazy[id*2+1]+=lazy[id];
d[id*2]+=lazy[id];
d[id*2+1]+=lazy[id];
lazy[id]=0;
}
}
void update(int id,int l,int r,int x,int y,int v){
if(x<=l&&r<=y){
d[id]+=v;
lazy[id]+=v;
return;
}
int mid=(l+r)/2;
pushdown(id);
if(x<=mid) update(id*2,l,mid,x,y,v);
if(y>mid) update(id*2+1,mid+1,r,x,y,v);
pushup(id);
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>q[i].l>>q[i].r;
a[++cnt]=q[i].l;
a[++cnt]=q[i].r;
q[i].len=q[i].r-q[i].l;
}
sort(q+1,q+n+1);
sort(a+1,a+cnt+1);
cnt=unique(a+1,a+cnt+1)-a-1;
for(int i=1;i<=n;i++){
q[i].l=lower_bound(a+1,a+cnt+1,q[i].l)-a;
q[i].r=lower_bound(a+1,a+cnt+1,q[i].r)-a;
}
int l=0;
for(int i=1;i<=n;i++){
update(1,1,cnt,q[i].l,q[i].r,1);
while(l<=i&&d[1]>=m){
if(l) update(1,1,cnt,q[l].l,q[l].r,-1);
ans=min(q[i].len-q[l].len,ans);
l++;
}
}
cout<<(ans==2e9?-1:ans);
return 0;
}