[USACO24OPEN] Grass Segments G

Luogu

IDLGP10281

Time2000ms

Memory256MB

DifficultyP6

USACO2024cdq 分治

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 The first line contains $N$. The next $N$ lines each contain three space-separated integers $\ell_i$, $r_i$, and $k_i$. ## Output The answers for all cultivars on separate lines. [samples] ## Note ##### For Sample 1: The overlaps of the cultivars is $[4,6]$, which has length $2$, which is at least $2$ but not at least $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$.

Samples

Input #1

2
3 6 3
4 7 2

Output #1

0
1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[USACO24OPEN] Grass Segments G",
    "description": {
      "content": "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 < \\e",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10281"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 < \\e...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments