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
| #include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
int n, m, num[1000005], tot;
struct Lines{
int l, r;
bool operator<(const Lines &u)const{
return r-l>u.r-u.l;
}
}l[500005];
struct SGT{
int zdz[4000005], tag[4000005];
void pushDown(int o, int lson, int rson){
zdz[lson] += tag[o];
zdz[rson] += tag[o];
tag[lson] += tag[o];
tag[rson] += tag[o];
tag[o] = 0;
}
void update(int o, int l, int r, int x, int y, int v){
if(l>=x && r<=y){
zdz[o] += v;
tag[o] += v;
}
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(tag[o]) pushDown(o, lson, rson);
if(x<=mid) update(lson, l, mid, x, y, v);
if(mid<y) update(rson, mid+1, r, x, y, v);
zdz[o] = max(zdz[lson], zdz[rson]);
}
}
}sgt;
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++){
scanf("%d %d", &l[i].l, &l[i].r);
num[++tot] = l[i].l; num[++tot] = l[i].r;
}
sort(num+1, num+1+tot);
tot = unique(num+1, num+1+tot) - num - 1;
sort(l+1, l+1+n);
int ll=1, re=0x3f3f3f3f;
for(int i=1; i<=n; i++){
l[i].l = lower_bound(num+1, num+1+tot, l[i].l)-num;
l[i].r = lower_bound(num+1, num+1+tot, l[i].r)-num;
sgt.update(1, 1, tot, l[i].l, l[i].r, 1);
while(sgt.zdz[1]>=m && ll<=i){
re = min(re, num[l[ll].r]-num[l[ll].l]-(num[l[i].r]-num[l[i].l]));
sgt.update(1, 1, tot, l[ll].l, l[ll].r, -1);
ll++;
}
}
if(re!=0x3f3f3f3f) cout<<re<<endl;
else cout<<"-1\n";
return 0;
}
|