这不是这题经典锅吗。
by muyang_233 @ 2022-09-30 15:07:29
每个区间左边和右边分别存的，所以要多乘一个 $2$。
by muyang_233 @ 2022-09-30 15:08:17
@[muyang_233](/user/113521) 对啊，那难道不是4*2吗
by Uvocde @ 2022-10-01 12:19:46
@[Uvocde](/user/111084)
一个区间 不止有左右
可能还有中间
所以是 3*4=12 倍
如果我错了请狠狠的D我
by Nephren_Sakura @ 2023-03-15 09:02:17
@[_Chtholly_Nephren_](/user/400783) 谢谢啦
by Uvocde @ 2023-03-16 00:39:37
啊啊？为啥我开 $8$ 倍就AC了？按说插入一个线段只会多出来 $2$ 个点吧，所以开 $8$ 倍就够了
```cpp
#include<bits/stdc++.h>
#define il inline
#define re register
#define ll long long
#define ull unsigned ll
#define uint unsigned int
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define IT iterator
#define pr pair
#define pq priority_queue
#define mpr make_pair
#define pii pr <int, int>
#define graph std :: vector <std :: pii>
#define int ll
const int N = 5e5 + 5, inf = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
il int R () {
int s = 0, f = 1; char ch = getchar();
while (!isdigit(ch)) f = (ch == '-') ? -1 : 1, ch = getchar();
while (isdigit(ch)) s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
return s * f;
}
int n, m, lsh[N << 1], lshtot, tot, ans = inf;
std :: umap <int, int> vis;
struct node {
int l, r, len;
bool operator < (const node &o) const {
return len < o.len;
}
}a[N];
struct segment_tree {
struct node {
int maxx, add;
}tree[N << 3];
il void pushup (int p) {
tree[p].maxx = std :: max(tree[p << 1].maxx, tree[p << 1 | 1].maxx);
return ;
}
il void pushdown (int p) {
tree[p << 1].add += tree[p].add, tree[p << 1].maxx += tree[p].add;
tree[p << 1 | 1].add += tree[p].add, tree[p << 1 | 1].maxx += tree[p].add;
tree[p].add = 0;
return ;
}
il void add (int p, int l, int r, int ql, int qr, int val) {
if (ql > r || qr < l) return ;
if (l >= ql && r <= qr) {
tree[p].add += val, tree[p].maxx += val;
return ;
}
int mid = (l + r) >> 1;
pushdown(p);
add(p << 1, l, mid, ql, qr, val), add(p << 1 | 1, mid + 1, r, ql, qr, val);
pushup(p);
return ;
}
il int query (int p, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return -inf;
if (l >= ql && r <= qr) return tree[p].maxx;
pushdown(p);
int mid = (l + r) >> 1;
return std :: max(query(p << 1, l, mid, ql, qr), query(p << 1 | 1, mid + 1, r, ql, qr));
}
}Tr;
signed main () {
n = R(), m = R();
for (int i = 1; i <= n; i++) {
int x = R(), y = R();
lsh[++lshtot] = x, lsh[++lshtot] = y, a[i] = {x, y, y - x + 1};
}
std :: sort(lsh + 1, lsh + lshtot + 1);
lsh[0] = -inf;
for (int i = 1; i <= lshtot; i++) {
if (lsh[i] != lsh[i - 1]) vis[lsh[i]] = ++tot;
}
for (int i = 1; i <= n; i++) a[i].l = vis[a[i].l], a[i].r = vis[a[i].r];
std :: sort(a + 1, a + 1 + n);
for (int l = 1, r = 0; l <= n; Tr.add(1, 1, tot, a[l].l, a[l].r, -1), l++) {
while (r < n && Tr.tree[1].maxx < m) ++r, Tr.add(1, 1, tot, a[r].l, a[r].r, 1);
if (Tr.tree[1].maxx >= m) ans = std :: min(ans, a[r].len - a[l].len);
}
return !printf("%lld\n", (ans == inf) ? (-1) : ans);
}
```
by 快速herself变换 @ 2023-09-13 08:29:25