Доброго времени суток. Есть такая задача — Лыжные гонки. Your text to link here...

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

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

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

1<=N<=500000, 1<=L<=10^9, 1<=Wi<=10^9

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

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

Ограничение по времени — 2 сек Ограничение по памяти — 128\256 мб(не нашёл информации)

Что я придумал по этой задаче : будем идти по порядку, увеличивая i. i лыжник обгонит j, если i>j и L*Wi < L*Wj-(i-j). Что из этого следует — будем хранить в каждой вершине дерева отрезков отсотрированный массив, который относится к этой части ДО (деревом Ропана это вроде зовётся). И потом на каждый запрос мы будем log(N)*log(n) отвечать на этот запрос, сколько есть таких чисел на отрезке [1;i-1]. И на каждой итерации мы будем отнимать единицу от отрезка предыдущего.

Но квадрат логарифма судя по всему не зайдет. А логарифм зайдет. Как я придумал, тут нужно писать каскадирование. Это нам по идее обеспечит нужную асимптотику.

В чём вопрос : верна ли эта мысль? Если верна, то можете ли рассказать подробнее про это самое каскадирование и как его писать, если можно. Я ни разу его не писал и смутно представляю, как это сделать.

И ещё — нет ли других решений данной задачи?

Заранее спасибо.