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
| #include <bits/stdc++.h> #define N 1000005 using namespace std;
template <typename T> inline void read(T &num) { T x = 0, f = 1; char ch = getchar(); for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1; for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0'); num = x * f; }
int n, m, len[N], srt[N], mx; struct intv { int l, r; } p[N]; bool cmp(intv x, intv y) { return x.r-x.l < y.r-y.l; }
void fCuCcFk() { for (int i = 1; i <= n; i++) srt[++mx] = p[i].l, srt[++mx] = p[i].r; sort(srt+1, srt+mx+1); mx = unique(srt+1, srt+mx+1) - srt - 1; for (int i = 1; i <= n; i++) { len[i] = p[i].r - p[i].l + 1; p[i].l = lower_bound(srt+1, srt+mx+1, p[i].l) - srt; p[i].r = lower_bound(srt+1, srt+mx+1, p[i].r) - srt; } }
struct segtree { int mx, tag; } tr[N<<2]; void build(int ind, int l, int r) { tr[ind].mx = tr[ind].tag = 0; if (l == r) return; int mid = (l + r) >> 1; build(ind<<1, l, mid); build(ind<<1|1, mid+1, r); } inline void pushdown(int ind) { if (!tr[ind].tag) return; int v = tr[ind].tag; tr[ind].tag = 0; tr[ind<<1].mx += v; tr[ind<<1].tag += v; tr[ind<<1|1].mx += v; tr[ind<<1|1].tag += v; } void update(int ind, int l, int r, int x, int y, int v) { if (x <= l && r <= y) { tr[ind].mx += v; tr[ind].tag += v; return; } pushdown(ind); int mid = (l + r) >> 1; if (x <= mid) update(ind<<1, l, mid, x, y, v); if (mid < y) update(ind<<1|1, mid+1, r, x, y, v); tr[ind].mx = max(tr[ind<<1].mx, tr[ind<<1|1].mx); }
int main() { read(n); read(m); for (int i = 1; i <= n; i++) { read(p[i].l); read(p[i].r); } sort(p + 1, p + n + 1, cmp); fCuCcFk(); int ans = 0x3f3f3f3f; build(1, 1, mx); update(1, 1, mx, p[1].l, p[1].r, 1); for (int i = 1, j = 1; i <= n; i++) { while (j < n && tr[1].mx < m) { j++; update(1, 1, mx, p[j].l, p[j].r, 1); } if (tr[1].mx >= m) ans = min(ans, len[j] - len[i]); update(1, 1, mx, p[i].l, p[i].r, -1); } printf("%d\n", ans == 0x3f3f3f3f ? -1 : ans); return 0; }
|