USACO 2024 US Open Contest, Gold

Problem 2. Grass Segments


Contest has ended.

Log in to allow submissions in analysis mode


Bessie is planting some grass on the positive real line. She has $N$ ($2\le N\le 2\cdot 10^5$) different cultivars of grass, and will plant the $i$th cultivar on the interval $[\ell_i, r_i]$ ($0 < \ell_i < r_i \leq 10^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 - \ell_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$.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $N$.

The next $N$ lines each contain three space-separated integers $\ell_i$, $r_i$, and $k_i$.

OUTPUT FORMAT (print output to the terminal / stdout):

The answers for all cultivars on separate lines.

SAMPLE INPUT:

2
3 6 3
4 7 2

SAMPLE OUTPUT:

0
1

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

SAMPLE INPUT:

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

SAMPLE OUTPUT:

3
3
2
2

SAMPLE INPUT:

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

SAMPLE OUTPUT:

0
3
1
3
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 2N$ for all $i$.

Problem credits: Benjamin Qi

Contest has ended. No further submissions allowed.