Grass Segments
플래티넘 I의견: 0
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\).
Problem credits: Benjamin Qi
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
The first line contains \(N\).
The next \(N\) lines each contain three space-separated integers \(\ell_i\), \(r_i\),
and
\(k_i\).
The answers for all cultivars on separate lines.
2
3 6 3
4 7 20
1The overlaps of the cultivars is \([4,6]\), which has length \(2\), which is at
least \(2\) but not at least \(3\).
4
3 6 1
2 5 1
4 10 1
1 4 13
3
2
25
8 10 2
4 9 2
3 7 4
5 7 1
2 7 10
3
1
3
3평가 및 의견
Grass Segments
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Grass Segments