#PU1426. USACO 2024 US Open Contest, Gold — Problem 2. Grass Segments

    ID: 1664 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:open24来源:usaco.orgscoring:equal_test_cases线段树排序

USACO 2024 US Open Contest, Gold — Problem 2. Grass Segments

USACO 2024 US Open Contest, Gold — Problem 2. Grass Segments

题目描述

Bessie is planting some grass on the positive real line. She has NN (2≤N≤2⋅1052\le N\le 2\cdot 10^5) different cultivars of grass, and will plant the iith cultivar on the interval [ℓi,ri][\ell_i, r_i] (0<ℓi<ri≤1090 < \ell_i < r_i \leq 10^9). In addition, cultivar ii grows better when there is some cultivar jj (j≠ij\neq i) such that cultivar jj and cultivar ii overlap with length at least kik_i (0<ki≤ri−ℓi0 < k_i \leq r_i - \ell_i). Bessie wants to evaluate all of her cultivars. For each ii, compute the number of j≠ij\neq i such that jj and ii overlap with length at least kik_i.

输入格式

The first line contains NN. The next NN lines each contain three space-separated integers ℓi\ell_i, rir_i, and kik_i.

输出格式

The answers for all cultivars on separate lines.

数据范围

(见题面原文)

样例

样例 1

2
3 6 3
4 7 2
0
1
The overlaps of the cultivars is $[4,6]$, which has length $2$, which is at
least $2$ but not at least $3$.

样例 2

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

样例 3

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