Bessie is planting some grass on the positive real line. She has N (2≤N≤2⋅105) different cultivars of grass, and will plant the ith cultivar on the interval [ℓi,ri](0<ℓi<ri≤109).
In addition, cultivar i grows better when there is some cultivar j (j≠i) such that cultivar j and cultivar i overlap with length at least ki (0<ki≤ri−ℓi). Bessie wants to evaluate all of her cultivars. For each i, compute the number of j≠i such that j and ioverlap with length at least ki.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N.
The next N lines each contain three space-separated integers ℓi, ri, and ki.
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≤5000
Inputs 6-11: k is the same for all intervals
Inputs 12-20: No additional constraints.
In addition, for Inputs 5, 7, ..., 19, ri≤2N for all i.
Problem credits: Benjamin Qi
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
