记录编号	417556	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2016]区间	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	6.014 s
提交时间	2017-06-25 22:29:59	内存使用	53.95 MiB

#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <cctype>
#include <list>
#include <queue>
#include <deque>
#include <vector>
using namespace std;
const int MAXN = 5e5+10;
struct node{
  int ls, rs, l, r;
  int maxv;
  int lazyadd;
  inline void add(int v){
    lazyadd += v;
    maxv += v;
  }
}ns[MAXN<<2];
const int root = 1;
int _last = root;
void pushup(node &d){
  d.maxv = max(ns[d.ls].maxv, ns[d.rs].maxv);
}
int build(int l, int r){
  if(l > r)return 0;
  int c = _last++;
  ns[c].l = l, ns[c].r = r;
  if(l < r){
    int m = (l+r)>>1;
    ns[c].ls = build(l, m);
    ns[c].rs = build(m+1, r);
    pushup(ns[c]);
  }
  return c;
} 
void pushdown(node &d){
  if(d.lazyadd){
    ns[d.ls].add(d.lazyadd);
    ns[d.rs].add(d.lazyadd);
    d.lazyadd = 0;
  }
}
void update(int c, int l, int r, int t){
  if(!c)return; 
  node &d = ns[c];
  if(d.l == l && d.r == r)
    d.add(t);
  else{
    pushdown(d);
    if(r <= ns[d.ls].r)update(d.ls, l, r, t);
    else if(l >= ns[d.rs].l)update(d.rs, l, r, t);
    else{
      update(d.ls, l, ns[d.ls].r, t);
      update(d.rs, ns[d.rs].l, r, t);
    }
    pushup(d);
  }
}
namespace IO{
  char buf[1<<18], *fs, *ft;
  inline char readc(){
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
  }
  inline int readint(){
    char c; int r;
    while(c = readc()){if(c >= '0' && c <= '9'){r = c^0x30;break;}}
    while(isdigit(c = readc()))r = (r<<3)+(r<<1)+(c^0x30);
    return r;
  }
  inline int read_string(char *str){
    int len = 1;char c;
    while(!isalpha(c = readc()));str[0] = c;
    while(isalpha(c = readc()))str[len++] = c;
    str[len] = 0;
    return len;
  }
};using IO::read_string; using IO::readint;
struct range{
  int l, r;
  inline int length()const{return r-l;}
  bool operator<(const range &rg)const{
    return length() < rg.length();
  }
}rs[MAXN];
namespace dec{
  int vals[MAXN<<1];
  int plim;
  void make_dec(){
    sort(vals+1, vals+plim+1);
    int t = unique(vals+1, vals+plim+1)-vals;
    plim = t-1;
  }
  inline int get(int v){
    return lower_bound(vals+1, vals+plim+1, v)-vals;
  }
}
int main(){
  freopen("interval.in", "r", stdin);
  freopen("interval.out", "w", stdout);
  int n = readint(); int m = readint();
  for(int i = 1; i <= n; i++){
    rs[i].l = readint(); rs[i].r = readint();
    dec::vals[++dec::plim] = rs[i].l;
    dec::vals[++dec::plim] = rs[i].r;
  }  
  dec::make_dec();
  build(1, dec::plim);
  sort(rs+1, rs+1+n);
  int ans = 2e9;
  int minlen = rs[1].length(), maxlen;
  for(int i = 1, j = 1; i <= n; i++){
    update(1, dec::get(rs[i].l), dec::get(rs[i].r), 1);
    maxlen = rs[i].length();
    while(ns[1].maxv >= m){
      ans = min(ans, maxlen-minlen);
      update(1, dec::get(rs[j].l), dec::get(rs[j].r), -1);
      minlen = rs[++j].length();
    }
  }
  if(ans == 2e9)ans = -1;
  printf("%d\n", ans);
  return 0;
}