记录编号	600225	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2016]区间	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	2.801 s
提交时间	2025-04-22 19:15:05	内存使用	6.18 MiB

#include <cstdio>
#include <algorithm>
#define ls(root) root << 1
#define rs(root) root << 1 | 1
using namespace std;

const int MAXN = 5e5 + 10; 

struct SEQ {
	int l, r;
	int len;
} seq[MAXN];

struct NODE {
	int maxx;
	int lazy;
} node[MAXN << 3];

void PushUp(int root) {
	node[root].maxx = max(node[ls(root)].maxx, node[rs(root)].maxx) + node[root].lazy;
}

void AddSeq(int root, int lt, int rt, int lq, int rq, int val) {
	if (lt == lq && rt == rq) {
		node[root].lazy += val;
		node[root].maxx += val;
		return ;
	}
	int mid = lt + ((rt - lt) >> 1);
	if (rq <= mid) {
		AddSeq(ls(root), lt, mid, lq, rq, val);
	} else if (lq > mid) {
		AddSeq(rs(root), mid + 1, rt, lq, rq, val);
	} else {
		AddSeq(ls(root), lt, mid, lq, mid, val);
		AddSeq(rs(root), mid + 1, rt, mid + 1, rq, val);
	}
	PushUp(root);
}

int n, m; 
int root;
int b[MAXN << 1], bcnt;
int ans = 0x7fffffff;

int main() {
	freopen("interval.in", "r", stdin);
	freopen("interval.out", "w", stdout);
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d %d", &seq[i].l, &seq[i].r);
		b[++bcnt] = seq[i].l, b[++bcnt] = seq[i].r;
		seq[i].len = seq[i].r - seq[i].l;
	}
	sort(b + 1, b + bcnt + 1);
	bcnt = unique(b + 1, b + bcnt + 1) - b - 1;
	sort(seq + 1, seq + n + 1, [](SEQ x, SEQ y) {return x.len < y.len;});
	for (int i = 1; i <= n; ++i) {
		seq[i].l = lower_bound(b + 1, b + bcnt + 1, seq[i].l) - b;
		seq[i].r = lower_bound(b + 1, b + bcnt + 1, seq[i].r) - b;
	}
	int l = 1, r = 0;
	while (l <= n) {
		while (r < n && node[1].maxx < m) {
			++r;
			AddSeq(1, 1, bcnt, seq[r].l, seq[r].r, 1);
		}
		if (r == n && node[1].maxx < m) break;
		ans = min(ans, seq[r].len - seq[l].len);
		AddSeq(1, 1, bcnt, seq[l].l, seq[l].r, -1);
		++l;
	}
	printf("%d", ans == 0x7fffffff ? -1 : ans);
	return 0;
}