Задача №115435. Трасса М-11
Новая скоростная автомобильная магистраль М-11 представляет собой бесконечную прямую.
На трассе расположены \(n\) остановочных пунктов, каждый из которых — зона отдыха или заправка. Каждый остановочный пункт задается своей координатой \(x_i\) и при этом никакие два остановочных пункта не находятся в одном и том же месте. Тройка остановочных пунктов \((i, j, k)\) называется удобной, если \(x_{i} < x_{j} < x_{k}\), в точках \(x_{i}\) и \(x_{k}\) расположены заправки, а в точке \(x_{j}\) — зона отдыха, и при этом расстояние между заправками не превосходит \(d\).
Одна команда из Москвы собирается поехать на ВКОШП по трассе М-11, и её руководителю стало интересно, сколько существует удобных троек остановок на пути.
В первой строке дано два натуральных числа \(n\) и \(d\) — количество остановочных пунктов и максимальное расстояние между заправками (\(3 \leq n \leq 5 \cdot 10^{5}\), \(2 \leq d \leq 10^{9}\)).
В следующих \(n\) строках даны остановочные пункты. Каждый остановочный пункт задается двумя целыми числами \(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)\).
8 5 1 1 2 0 3 1 6 0 7 0 8 1 15 1 19 1
3
10 6 0 1 1 0 3 1 4 0 5 1 8 1 10 0 11 0 14 1 18 1
7