2050: [USACO 2024 US Open Contest Gold] Problem 2. Grass Segments

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\le {10}^9$).

In addition, cultivar $i$ grows better when there is some cultivar $j$ ($j\ne i$) such that cultivar $j$ and cultivar $i$ overlap with length at least $k_i$ ($0<k_i\le r_i-{\ell }_i$). Bessie wants to evaluate all of her cultivars. For each $i$, compute the number of $j\ne i$ such that $j$ and $i$ overlap with length at least $k_i$.

The next $N$ lines each contain three space-separated integers ${\ell }_i$, $r_i$, and $k_i$.

2
3 6 3
4 7 2

0
1