| Codeforces Round 487 (Div. 2) |
|---|
| Закончено |
— Сложно возможно затмить свет луны. Тени лишь раскрывают ее красоту и мягкость, — пропел Мино.
— Видишь? Облака, — сказал Канно, вглядываясь вдаль.
— Не может быть ничего лучше, — обернулся Мино к Канно.
Представим небо как координатную ось. Луна находится в начале координат, то есть в точке с координатой $$$0$$$.
В небе есть $$$n$$$ облаков. Все облака имеют одинаковую длину $$$l$$$. $$$i$$$-е облако изначально покрывает отрезок $$$(x_i, x_i + l)$$$ (не включая границы). Изначально облако двигается со скоростью $$$v_i$$$, которая равна либо $$$1$$$, либо $$$-1$$$.
Изначально никакие два облака не пересекаются, то есть для всех $$$1 \leq i \lt j \leq n$$$ выполняется $$$\lvert x_i - x_j \rvert \geq l$$$.
Если скорость ветра равна $$$w$$$, то скорость $$$i$$$-го облака станет равна $$$v_i + w$$$, то есть его координаты будут увеличиваться на $$$v_i + w$$$ за единицу времени. Обратите внимание, ветер может быть достаточно сильным и направления движения облаков могут изменяться.
Помогите Мино, подсчитайте число пар $$$(i, j)$$$ ($$$i < j$$$) таких, что существует такая скорость ветра $$$w$$$, не превышающая $$$w_\mathrm{max}$$$ по модулю (возможно, отрицательная и/или вещественная) такая, что $$$i$$$-е и $$$j$$$-е облака в какой-то момент будут оба закрывать луну. Скорость ветра $$$w$$$ может быть различной для различных пар.
Первая строка содержит три целых числа $$$n$$$, $$$l$$$ и $$$w_\mathrm{max}$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq l, w_\mathrm{max} \leq 10^8$$$) — количество облаков, длина каждого облака и максимально возможная скорость ветра, соответственно.
$$$i$$$-я из следующих $$$n$$$ строк содержит два целых числа $$$x_i$$$ и $$$v_i$$$ ($$$-10^8 \leq x_i \leq 10^8$$$, $$$v_i \in \{-1, 1\}$$$) — начальная позиция и скорость $$$i$$$-го облака, соответственно.
Гарантируется, что для всех $$$1 \leq i \lt j \leq n$$$ выполняется $$$\lvert x_i - x_j \rvert \geq l$$$.
Выведите одно целое число — количество неупорядоченных пар облаков таких, что они могут закрыть луну в один и тот же момент при некотором выборе скорости ветра $$$w$$$.
5 1 2
-2 1
2 1
3 -1
5 -1
7 -1
4
4 10 1
-20 1
-10 -1
0 1
10 -1
1
В первом примере начальные позиции и скорости облаков проиллюстрированы на рисунке ниже.
Пары облаков, которые могут одновременно закрыть луну:
- $$$(1, 3)$$$ закроют луну в момент времени $$$2.5$$$ при $$$w = -0.4$$$;
- $$$(1, 4)$$$ закроют луну в момент времени $$$3.5$$$ при $$$w = -0.6$$$;
- $$$(1, 5)$$$ закроют луну в момент времени $$$4.5$$$ при $$$w = -0.7$$$;
- $$$(2, 5)$$$ закроют луну в момент времени $$$2.5$$$ при $$$w = -2$$$.
На рисунке ниже приведены положения облаков в момент времени $$$2.5$$$ при скорости ветра $$$w = -0.4$$$. В этот момент $$$1$$$-е и $$$3$$$-е облака оба закрывают луну.
Во втором примере только пара $$$(1, 4)$$$ закроют луну в момент времени $$$15$$$ при скорости ветра $$$w = 0$$$.
Обратите внимание, что все времена и скорости ветра в примечании даны для примера, на самом деле существует бесконечное число способов выбрать их.
