CF989D A Shade of Moonlight

黑暗笼罩着树林和世界，月亮把光洒在小船和河流上。“要遮住月光几乎是不可能的，阴影展现了它温柔的美和安宁的本性。”Mino吟诵道。 “看到了吗？云来了。”Kanno望向远方。 “那再好不过了。”Mino转向Kanno。 天空可以看作是一条一维坐标轴。月亮位于原点，坐标为 $0$。 天空中有 $n$ 朵云，每朵云的长度都是 $l$。第 $i$ 朵云初始时覆盖区间 $(x_i, x_i + l)$（不包含端点）。初始时，它以速度 $v_i$ 移动，其中 $v_i$ 只能取 $1$ 或 $-1$。 此外，任意两朵云初始时都没有重叠，即对于所有 $1 \leq i < j \leq n$，都有 $|x_i - x_j| \geq l$。 风速为 $w$ 时，第 $i$ 朵云的速度变为 $v_i + w$。也就是说，每经过一个单位时间，它的坐标会增加 $v_i + w$。注意，风可以很大，云的运动方向也可能改变。 你需要帮助 Mino 统计有多少对 $(i, j)$（$i < j$），使得存在一个绝对值不超过 $w_\mathrm{max}$ 的风速 $w$（可以为负数或小数），使得第 $i$ 朵云和第 $j$ 朵云在某一未来时刻同时覆盖月亮。对于不同的云对，$w$ 可以不同。

第一行包含三个用空格分隔的整数 $n$、$l$ 和 $w_\mathrm{max}$（$1 \leq n \leq 10^5$，$1 \leq l, w_\mathrm{max} \leq 10^8$）——云的数量、每朵云的长度以及最大风速。 接下来的 $n$ 行中，第 $i$ 行包含两个用空格分隔的整数 $x_i$ 和 $v_i$（$-10^8 \leq x_i \leq 10^8$，$v_i \in \{-1, 1\}$）——第 $i$ 朵云的初始位置和速度。 输入保证对于所有 $1 \leq i < j \leq n$，都有 $|x_i - x_j| \geq l$。

输出一个整数，表示有多少对无序云对，使得存在合适的风速 $w$，使得每对云都能在某一时刻同时覆盖月亮。

在第一个样例中，云的初始位置和速度如下图所示。  满足条件的云对有： - $(1, 3)$，在 $w = -0.4$，时间 $2.5$ 时同时覆盖月亮； - $(1, 4)$，在 $w = -0.6$，时间 $3.5$ 时同时覆盖月亮； - $(1, 5)$，在 $w = -0.7$，时间 $4.5$ 时同时覆盖月亮； - $(2, 5)$，在 $w = -2$，时间 $2.5$ 时同时覆盖月亮。 下图为 $w = -0.4$，时间 $2.5$ 时云的位置，此时第 $1$ 朵和第 $3$ 朵云同时覆盖月亮。  在第二个样例中，唯一满足条件的云对是 $(1, 4)$，在 $w = 0$，时间 $15$ 时同时覆盖月亮。 注意，上述时间和风速仅为示例，实际上可能有无穷多种选择。 由 ChatGPT 4.1 翻译