当前没有测试数据。

USACO 2024 US Open Contest, Gold Problem 2: Grass Segments

I. Problem Description

1. Grass Planting Situation

Bessie is planting some grass on the positive real line. She has $N$ ($2\leq N\leq 2\cdot10^{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}$).

2. Growth Condition

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}$).

3. Task

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}$.

II. Input Format

1. The first line contains $N$.
2. The next $N$ lines each contain three space-separated integers $\ell_{i}$, $r_{i}$, and $k_{i}$.

III. Output Format

The answers for all cultivars on separate lines.

IV. Sample Input and Output

Sample 1

• Input
  • 2
  • 3 6 3
  • 4 7 2
• Output
  • 0
  • 1
• Explanation The overlaps of the cultivars is $[4, 6]$, which has length $2$, which is at least $2$ but not at least $3$.

Sample 2

• Input
  • 4
  • 3 6 1
  • 2 5 1
  • 4 10 1
  • 1 4 1
• Output
  • 3
  • 3
  • 2
  • 2

Sample 3

• Input
  • 5
  • 8 10 2
  • 4 9 2
  • 3 7 4
  • 5 7 1
  • 2 7 1
• Output
  • 0
  • 3
  • 1
  • 3
  • 3

V. Scoring Rules

1. Input 4 - 5: $N\leq 5000$.
2. Inputs 6 - 11: $k$ is the same for all intervals.
3. Inputs 12 - 20: No additional constraints.
   • In addition, for Inputs 5, 7, $\cdots$, 19, $r_{i}\leq 2N$ for all $i$.

VI. Problem Source

Problem credits: Benjamin Qi.