Страница: 1 Отображать по:
#3335
Лыжные гонки
  

Во время лыжных соревнований \(N\) спортсменов стартуют с интервалом в 1 минуту. Скорость каждого лыжника на дистанции постоянна: \(i\)-й лыжник преодолевает 1 км за \(w_i\) минут. Длина трассы равна \(L\) км. Считается, что \(i\)-й лыжник обогнал \(j\)-го (совершил обгон), если он стартовал позже \(j\)-го, а пришёл к финишу раньше него. Подсчитайте суммарное число совершённых во время гонки обгонов.

Входные данные

Первая строка входного файла содержит два целых числа \(N\) и \(L\). Во второй строке через пробел расположены \(N\) целых чисел \(w_i\).

Выходные данные

Выведите единственное число - суммарное количество обгонов.

Примечания

Во всех тестах \(1 \le L \le 10^9\), \(1 \le w_i \le 10^9\) при \(i = 1, 2, \dots, N\). Тесты состоят из трёх групп.

  1. Тесты 1 и 2 из условия, оцениваются в 0 баллов.
  2. В тестах этой группы \(1 \le N \le 10\,000\), эти тесты оцениваются в 50 баллов, при этом баллы начисляются только при прохождении всех тестов группы.
  3. Off-line группа, \(1 \le N \le 500\,000\). При этом баллы за тесты этой группы ставятся только тогда, когда программа проходит все тесты предыдущей группы. Если программа не проходит хотя бы один из тестов группы 1, то баллы за тесты группы 2 не ставятся. Тесты этой группы оцениваются независимо друг от друга.
Примеры
Входные данные
2 1
20 19
Выходные данные
0
Входные данные
5 3
3 6 2 4 1
Выходные данные
7
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест