Grass Segments | Code Joint

Bessie is planting some grass on the positive real line. She has $N$ ( $2 \leq N \leq 2 \cdot 1 0^{5}$ ) different cultivars of grass, and will plant the $i$ th cultivar on the interval $[ℓ_{i}, r_{i}]$ ( $0 < ℓ_{i} < r_{i} \leq 1 0^{9}$ ).

In addition, cultivar $i$ grows better when there is some cultivar $j$ ( $j \neq = i$ ) such that cultivar $j$ and cultivar $i$ overlap with length at least $k_{i}$ ( $0 < k_{i} \leq r_{i} - ℓ_{i}$ ). Bessie wants to evaluate all of her cultivars. For each $i$ , compute the number of $j \neq = i$ such that $j$ and $i$ overlap with length at least $k_{i}$ .

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

SCORING:

Input 4-5: $N \leq 5000$
Inputs 6-11: $k$ is the same for all intervals
Inputs 12-20: No additional constraints.

In addition, for Inputs 5, 7, ..., 19, $r_{i} \leq 2 N$ for all $i$ .

Problem credits: Benjamin Qi

Source: USA Computing Olympiad.

Input Format

The first line contains $N$ .

The next $N$ lines each contain three space-separated integers $ℓ_{i}$ , $r_{i}$ , and $k_{i}$ .

Output Format

The answers for all cultivars on separate lines.

Sample Input 1

2 3 6 3 4 7 2

Sample Output 1

0 1

Sample Input 2

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

Sample Output 2

3 3 2 2

Sample Input 3

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

Sample Output 3

0 3 1 3 3

Submit

Language