某地检测发现共存在 N 处污染点,各污染点分布在一条直线道路上。将该道路建立数轴模型,第 i 处污染点位于坐标 P_i,其污染指数为 V_i。
环境保护团队配备了一套土壤修复装置。每次使用时,需将装置部署在道路上某一坐标 x 处。装置激活后,将对以 x 为中心、半径为 D 的区间 [x-D,\ x+D] 内的所有污染点同时施加处理,使各污染点的污染指数降低 A。位于区间外的污染点不受影响。
当某个污染点的污染指数降至 0,则该污染点被修复,如果该位置再次位于修复装置处理的区间内,该位置的污染指数不会再降低。
当且仅当所有污染点的污染指数均降至 0 时,该地带视为完成修复。
请你计算:在最优部署策略下,完成全部修复所需的最少装置激活次数。
第一行包含三个整数 N,D,A,分别表示污染点数量、装置的覆盖半径和单次激活的处理强度。
接下来 N 行,每行包含两个整数 P_i 和 V_i,分别表示第 i 处污染点的坐标及其初始污染指数。
输出一个整数,表示完成修复所需的最少激活次数。
3 3 2 1 2 5 4 9 2
2
9 4 1 1 5 2 4 3 3 4 2 5 1 6 2 7 3 8 4 9 5
5
3 0 1 300000000 1000000000 100000000 1000000000 200000000 1000000000
3000000000
样例 #1:
三处污染点坐标依次为 1, 5, 9,污染指数依次为 2, 4, 2,装置覆盖半径 D=3,每次处理强度 A=2。
两次激活后所有污染点清零,可以证明 1 次激活无法完成修复,故答案为 2。
| 测试点编号 | N,D,A |
|---|---|
| 1 | N=1, D \leq 10^9, A=1 |
| 2 | N=1, D \leq 10^9, A=2 |
| 3 \sim 4 | N \leq 2 \times 10^5, D=0, A=1 |
| 5 \sim 10 | N \leq 2 \times 10^5, D \leq 10^9, A \leq 10^9 |
对于 100\% 的数据,满足 1 \leq N \leq 2\times 10^5,0 \leq D \leq 10^9,1 \leq A \leq 10^9,0 \leq P_i \leq 10^9,1 \leq V_i \leq 10^9,测试数据保证所有 P_i 互不相同。