Grass Segments

题目描述

Bessie 正在正实数轴上种植一些草。她有 $N$（$2\le N\le 2\cdot 10^5$）种不同的草品种，并会在区间 $[\ell_i, r_i]$（$0 < \ell_i < r_i \leq 10^9$）上种植第 $i$ 个品种。

此外，当存在某个品种 $j$（$j\neq i$）使得品种 $j$ 与品种 $i$ 的重叠长度至少为 $k_i$（$0 < k_i \leq r_i - \ell_i$）时，品种 $i$ 会生长得更好。Bessie 想评估她的所有品种。对于每个 $i$，计算满足 $j\neq i$ 且 $j$ 与 $i$ 的重叠长度至少为 $k_i$ 的 $j$ 的数量。

输入格式

第一行包含 $N$。 接下来 $N$ 行每行包含三个用空格分隔的整数 $\ell_i$、$r_i$ 和 $k_i$。

输出格式

将所有品种的答案分别输出，每个答案占一行。

2
3 6 3
4 7 2

0
1

4
3 6 1
2 5 1
4 10 1
1 4 1

3
3
2
2

5
8 10 2
4 9 2
3 7 4
5 7 1
2 7 1

0
3
1
3
3

提示

品种的重叠部分是 $[4,6]$，其长度为 $2$，至少为 $2$ 但不至少为 $3$。

评分： 输入 4-5：$N \leq 5000$ 输入 6-11：所有区间的 $k$ 都相同 输入 12-20：无额外限制。

另外，对于输入 5, 7, ..., 19，所有 $i$ 都满足 $r_i \leq 2N$。

题目来源致谢：Benjamin Qi

标签: USACO|2024|Gold

来源

USACO|2024|Gold