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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
| #include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
namespace SegmentTree{
struct node{
int l,r;
int val,tag;
}tree[MAXN<<2];
#define lc i<<1
#define rc i<<1|1
inline void pushup(int i){
tree[i].val=max(tree[lc].val,tree[rc].val);
}
inline void Change(int i,int val){
tree[i].tag+=val;
tree[i].val+=val;
}
inline void pushdown(int i){
if (tree[i].tag){
Change(lc,tree[i].tag);
Change(rc,tree[i].tag);
tree[i].tag=0;
}
}
void Build(int i,int l,int r){
tree[i].l=l,tree[i].r=r;
tree[i].val=tree[i].tag=0;
if (l==r) return ;
int mid=(l+r)>>1;
Build(lc,l,mid);
Build(rc,mid+1,r);
}
void Update(int i,int L,int R,int val){
if (L<=tree[i].l&&tree[i].r<=R){
Change(i,val);
return ;
}
int mid=(tree[i].l+tree[i].r)>>1;
pushdown(i);
if (L<=mid) Update(lc,L,R,val);
if (mid<R) Update(rc,L,R,val);
pushup(i);
}
int Query(int i,int L,int R){
if (L<=tree[i].l&&tree[i].r<=R){
return tree[i].val;
}
int mid=(tree[i].l+tree[i].r)>>1,ans=-0x7fffffff;
pushdown(i);
if (L<=mid) ans=max(ans,Query(lc,L,R));
if (mid<R) ans=max(ans,Query(rc,L,R));
return ans;
}
}
using namespace SegmentTree;
struct Segment{
int l,r,len;
}p[MAXN];
inline bool operator < (Segment A,Segment B){
return A.len<B.len;
}
int n,m;
int num[MAXN<<1],cnt,maxn;
inline void discrete(){
sort(num+1,num+1+cnt);
cnt=unique(num+1,num+1+cnt)-num-1;
for (register int i=1;i<=n;++i){
p[i].l=lower_bound(num+1,num+1+cnt,p[i].l)-num;
p[i].r=lower_bound(num+1,num+1+cnt,p[i].r)-num;
maxn=max(maxn,p[i].l);
maxn=max(maxn,p[i].r);
}
}
int main(){
n=read(),m=read();
for (register int i=1;i<=n;++i){
int l=read(),r=read();
p[i]=Segment{l,r,r-l};
num[++cnt]=l,num[++cnt]=r;
}
discrete();
sort(p+1,p+1+n);
int ans=0x7fffffff;
int pl=1,pr=0;
Build(1,1,maxn);
while (true){
while (pr<=n){
if (Query(1,1,maxn)>=m) break;
pr++;
Update(1,p[pr].l,p[pr].r,1);
}
if (Query(1,1,maxn)<m) break;
while (pl<=pr){
if (Query(1,1,maxn)<m) break;
ans=min(ans,p[pr].len-p[pl].len);
Update(1,p[pl].l,p[pl].r,-1);
pl++;
}
}
printf("%d\n",ans==0x7fffffff?-1:ans);
}
|
