注意到按长度排序之后，显然是有决策单调性的，故可以双指针。
判定的话随便扯个数据结构维护一下（
感觉在 NOI 里面算签到题？
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
using namespace std;
const int N = 5e5;
int n,m;
int ind[2 * N + 5],len;
int ans = 0x3f3f3f3f;
struct note
{
int l,r,len;
inline bool operator<(const note &o) const
{
return len < o.len;
}
} a[N + 5];
struct node
{
int max,tag;
} seg[(N << 3) + 10];
void update(int l,int r,int k,int p,int tl,int tr)
{
if(l <= tl && tr <= r)
{
seg[p].max += k,seg[p].tag += k;
return ;
}
int mid = tl + tr >> 1;
l <= mid && (update(l,r,k,ls,tl,mid),1);
r > mid && (update(l,r,k,rs,mid + 1,tr),1);
seg[p].max = max(seg[ls].max,seg[rs].max) + seg[p].tag;
}
int query(int l,int r,int p,int tl,int tr)
{
if(l <= tl && tr <= r)
return seg[p].max;
int mid = tl + tr >> 1;
int ret = 0;
l <= mid && (ret = max(ret,query(l,r,ls,tl,mid)));
r > mid && (ret = max(ret,query(l,r,rs,mid + 1,tr)));
return ret + seg[p].tag;
}
int main()
{
scanf("%d%d",&n,&m);
for(register int i = 1;i <= n;++i)
scanf("%d%d",&a[i].l,&a[i].r),a[i].len = a[i].r - a[i].l,ind[++len] = a[i].l,ind[++len] = a[i].r;
sort(ind + 1,ind + len + 1),len = unique(ind + 1,ind + len + 1) - ind - 1;
for(register int i = 1;i <= n;++i)
a[i].l = lower_bound(ind + 1,ind + len + 1,a[i].l) - ind,a[i].r = lower_bound(ind + 1,ind + len + 1,a[i].r) - ind;
sort(a + 1,a + n + 1),a[0].len = -0x3f3f3f3f;
for(register int i = 1,j = 0;i <= n;++i)
{
update(a[i].l,a[i].r,1,1,1,len);
for(;j < i && seg[1].max >= m;++j,update(a[j].l,a[j].r,-1,1,1,len));
ans = min(ans,a[i].len - a[j].len);
}
printf("%d\n",ans ^ 0x3f3f3f3f ? ans : -1);
}