У меня есть 10^6 отрезков, имеющих длину t[i]. Их левые концы можно расположить с l[i] до r[i]

Нужно определить, можно ли все отрезки разместить на прямой без пересечений

Подойдёт ли сорт по правой границе?

Кажется да

Я забыл, я уже спрашивал, пытался ли кто-нибудь реализовать олимпиадную геометрию полностью проективно? То есть точки и прямые один и тот же тип

вроде да

всем привет)) помогите решить,пожалуйста

Рик и Морти снова бороздят просторы вселенных, но решили ограничиться только теми, номера которых меньше M. Они могут телепортироваться из вселенной с номером z во вселенную (z+1) mod M за a бутылок лимонада или во вселенную (z2+1) mod M за b бутылок лимонада. Рик и Морти хотят добраться из вселенной с номером x во вселенную с номером y. Сколько бутылок лимонада отдаст Рик за такое путешествие, если он хочет потратить их как можно меньше?

ограничения?

дайкстра?

z2 - это z^2?

Да

Тогда видимо дейкстра, как выше предлагают - за O(M*log(M))
Можно относительно несложно ускорить до O(M) с двумя очередями, а вот meet-in-the-middle будет сложно из-за того что нужно считать корень, зато потенциально можно получить решение  за O(sqrt(M))

А сейчас на M как будут ограничения в 1е9...

Если A=B+1  можно БФС с дополнением вершин

А если А=Б то вообще БФС

не сказано, что a и b неотрицательные

вот покупаешь фьючерсы на WTI за -37 бутылок лемонада

Если отрицательные то можем гонять по кругу, не?

(насчёт b не уверен)