Lvat_s Blog

two points+线段树

按长度排序之后一个个加就行

我考场上居然没想到

数组开小wa了2次……身败名裂

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=500005,INF=1000000000;

int b[N<<1],n,m,cnt,ans=INF,tot;

struct Inside{
int l,r,len;
friend bool operator<(const Inside &A,const Inside &B){return A.len<B.len;}
}ins[N];

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

struct SegTree{
int l,r,tag,cnt;
}tree[N<<3];

inline void Pushup(const int &rt){
tree[rt].cnt=tree[rt].tag+max(tree[rt<<1].cnt,tree[rt<<1|1].cnt);
}

void Build(int rt,int l,int r){
tree[rt].l=l;tree[rt].r=r;
if(l==r)return;
int mid=l+r>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
}

void Add(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r){tree[rt].cnt++;tree[rt].tag++;return;}
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Add(rt<<1,l,r);
if(r>mid)Add(rt<<1|1,l,r);
Pushup(rt);
}

void Del(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r){tree[rt].cnt--;tree[rt].tag--;return;}
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Del(rt<<1,l,r);
if(r>mid)Del(rt<<1|1,l,r);
Pushup(rt);
}

int main(){
freopen("222.in","r",stdin);
freopen("222.out","w",stdout);
Read(n);Read(m);
for(int i=1;i<=n;i++){
	Read(ins[i].l);Read(ins[i].r);
	ins[i].len=ins[i].r-ins[i].l;
	b[++cnt]=ins[i].l;b[++cnt]=ins[i].r;
}
sort(b+1,b+cnt+1);
cnt=unique(b+1,b+cnt+1)-b-1;
for(int i=1;i<=n;i++)ins[i].l=lower_bound(b+1,b+cnt+1,ins[i].l)-b,ins[i].r=lower_bound(b+1,b+cnt+1,ins[i].r)-b;
sort(ins+1,ins+n+1);
Build(1,1,cnt);
int cur=0;
for(int i=1;i<=n;i++){
    while(cur<n && tree[1].cnt<m){cur++;Add(1,ins[cur].l,ins[cur].r);}
    if(tree[1].cnt<m)break;
    ans=min(ans,ins[cur].len-ins[i].len);
    Del(1,ins[i].l,ins[i].r);
}
printf("%d\n",ans==INF?-1:ans);
return 0;
}