gold_Grass_Segments (USACO US_Open_Contest)
Time limit: 2 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: data structures, line sweep, segment tree, coordinate compression, offline queries

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

Starter code:

Grader code:

Setup script:

Evaluation script: