P13970 [VKOSHP 2024] M-11 Highway

新建的高速公路 M-11 是一条无限长的直线。 在这条公路上有 $n$ 个停车点，每个停车点要么是休息区，要么是加油站。每个停车点由其坐标 $x_i$ 定义，且没有两个停车点位于同一位置。一个停车点三元组 $(i, j, k)$ 被称为“方便的”，如果满足 $x_{i} < x_{j} < x_{k}$，且 $x_{i}$ 和 $x_{k}$ 处都是加油站，$x_{j}$ 处是休息区，并且两个加油站之间的距离不超过 $d$。 一支来自莫斯科的队伍计划沿 M-11 高速公路前往比赛，其领队对沿途有多少个方便的停车点三元组产生了兴趣。

第一行包含两个正整数 $n$ 和 $d$ —— 停车点的数量和加油站之间的最大距离（$3 \leq n \leq 5 \cdot 10^{5}$，$2 \leq d \leq 10^{9}$）。 接下来的 $n$ 行，每行描述一个停车点。每个停车点由两个整数 $x_i$ 和 $t_i$ 构成 —— $x_i$ 表示该点的坐标，$t_i$ 表示该点的类型。类型 $0$ 表示休息区，类型 $1$ 表示加油站（$-10^{18} \leq x_i \leq 10^{18}$，$t_{i} \in \{0, 1\}$）。保证所有停车点的坐标严格递增。

输出一个整数，表示方便的三元组的数量。

在第一个输入样例中，方便的三元组有 $(1, 2, 3)$、$(3, 4, 6)$ 和 $(3, 5, 6)$。 由 ChatGPT 4.1 翻译