Eva

Time Limit: 60 Sec  Memory Limit: 256 MB
Submit: 1646  Solved: 898
Description

在数轴上有 n个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间，使得这 m个区间共同包含至少一个位置。换句话说，就是使得存在一个 x，使得对于每一个被选中的区间 [li,ri]，都有 li≤x≤ri。

对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li，即等于它的右端点的值减去左端点的值。

求所有合法方案中最小的花费。如果不存在合法的方案，输出 −1。

Input

第一行包含两个正整数 n,m用空格隔开，意义如上文所述。保证 1≤m≤n

接下来 n行，每行表示一个区间，包含用空格隔开的两个整数 li 和 ri 为该区间的左右端点。

N<=500000,M<=200000,0≤li≤ri≤10^9

Output 

只有一行，包含一个正整数，即最小花费。

Sample Input

6 3
3 5
1 2
3 4
2 2
1 5
1 4

Sample Output

2

离散化+按长度排序并以线段树的方式更新覆盖+更新答案即可

/**************************************************************

    Problem: 4653

    User: ictsing

    Language: C++

    Result: Accepted

    Time:11276 ms

    Memory:67704 kb

****************************************************************/

 

//BZOJ4653 [Noi2016]区间

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int mt = 1000000+5;

struct qwq{

    int x,id;

}p[mt<<1];

struct ques{

    int l,r,len;

}q[mt];

int h[mt<<1];

bool cmp(qwq a,qwq b)

{

    return a.x<b.x;

}

bool cmpp(ques a,ques b)

{

    return a.len<b.len;

}

int tree[mt<<2];

int add[mt<<2];

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

       ch=getchar();

       if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

       num=num*10+ch-'0';

       ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

void pushup(int rt)

{

    if(rt)

    {

        tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);

    }

}

void pushdown(int rt)

{

    if(rt&&add[rt])

    {

        add[rt<<1]+=add[rt];

        add[rt<<1|1]+=add[rt];

        tree[rt<<1]+=add[rt];

        tree[rt<<1|1]+=add[rt];

        add[rt]=0;

    }

}

void update(int rt,int l,int r,int lft,int rgt,int val)

{

    if(lft<=l&&r<=rgt)

    {

        add[rt]+=val;

        tree[rt]+=val;

        return ;

    }

    pushdown(rt);

    int mid=(l+r)>>1;

    if(lft<=mid) update(rt<<1,l,mid,lft,rgt,val);

    if(rgt>mid) update(rt<<1|1,mid+1,r,lft,rgt,val);

    pushup(rt);

}

int main()

{

    int n=read(),m=read();

    for(int i=1;i<=n;i++)

        p[2*i-1].x=read(),p[2*i].x=read(),p[i*2-1].id=2*i-1,p[i*2].id=i*2,q[i].len=p[i*2].x-p[i*2-1].x;

    sort(p+1,p+2*n+1,cmp);

    int k=0;

    for(int i=1;i<=2*n;i++)

    {

        if(p[i].x==p[i-1].x) h[p[i].id]=k;

        else h[p[i].id]=++k;

    }

    for(int i=1;i<=n;i++)

    {

        q[i].l=h[2*i-1],q[i].r=h[2*i];

    }

    sort(q+1,q+n+1,cmpp);

    int point=0;

    int ans=2e9;

    for(int i=1;i<=n;i++)

    {

        //cout<<q[i].l<<" "<<q[i].r<<" "<<point<<endl;

        //cout<<tree[1]<<endl;

        while(point<n&&tree[1]<m)

        {

            point++;

            update(1,1,k,q[point].l,q[point].r,1);

            //cout<<tree[1]<<" qwq "<<endl;

        }

        if(tree[1]>=m) 

        {

            ans=min(ans,q[point].len-q[i].len);

        }       

        update(1,1,k,q[i].l,q[i].r,-1);

    }

    if(ans!=2e9) printf("%d\n",ans);

    else puts("-1");

    return 0;

}