当前没有测试数据。

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

一、题目描述

1. 种草情况

贝西（Bessie）正在正实数轴上种草。她有N（$2\leq N\leq 2\cdot10^{5}$）种不同的草种，并且会将第i种草种在区间$[\ell_{i}, r_{i}]$（$0 < \ell_{i} < r_{i}\leq 10^{9}$）上。

2. 生长条件

此外，当存在某个草种j（j≠i），使得草种j和草种i重叠部分的长度至少为k_{i}（$0 < k_{i}\leq r_{i}-\ell_{i}$）时，草种i生长得更好。

3. 任务

贝西想要评估她所有的草种。对于每个i，计算满足j≠i且j和i重叠部分长度至少为k_{i}的j的数量。

二、输入格式

1. 第一行包含N。
2. 接下来的N行，每行包含三个用空格分隔的整数$\ell_{i}$、$r_{i}$和$k_{i}$。

三、输出格式

每个草种的答案单独占一行。

四、样例输入输出

样例1

• 输入
  • 2
  • 3 6 3
  • 4 7 2
• 输出
  • 0
  • 1
• 解释 两种草种的重叠部分是$[4, 6]$，其长度为2，至少为2但小于3。

样例2

• 输入
  • 4
  • 3 6 1
  • 2 5 1
  • 4 10 1
  • 1 4 1
• 输出
  • 3
  • 3
  • 2
  • 2

样例3

• 输入
  • 5
  • 8 10 2
  • 4 9 2
  • 3 7 4
  • 5 7 1
  • 2 7 1
• 输出
  • 0
  • 3
  • 1
  • 3
  • 3

五、评分规则

1. 输入4 - 5：$N\leq 5000$。
2. 输入6 - 11：所有区间的k相同。
3. 输入12 - 20：无其他额外限制。
   • 此外，对于输入5、7、…、19，所有i都有$r_{i}\leq 2N$。

六、题目来源

题目作者：本杰明·齐（Benjamin Qi）。