А вот почему.

Недостаточно глубоко прямой эфир просмотрел, да

Прям как у вас на полуфинале :-)

Дальше 500, футболки 1000.

500 и 1000

На А можно было сортонуть все рейсы, потом идти слева на право, хранить сколько человек должны выйти на каждой станции, и сколько есть каждых карточек. Когда нужно кому-то выходить, то жадно отдаем самые новые карточки.

Разбор доступен сразу после контеста в dashboard.

В A — тупая жадность.

Для начала посчитаем сколько будет потрачено, если никто не будет меняться карточками. Это делается тривиально, если использовать формулу суммы арифметической прогрессии.

Теперь найдем, сколько потратить можно, если оптимально передавать карточки. Заведем массив событий, в котором будем хранить для каждой станции метро (из тех, что есть во входных данных) сколько человек заходят и выходят на этой станции. Всего таких событий будет не более 2·M. Дальше будем идти по событиям. Когда люди где-то выходят, то им выгодно выйти с карточкой, которая в пути как можно меньше времени из тех, что еще не сданы при выходе. То есть надо использовать карточки, которые были взяты при входе на как можно более поздних станциях. Ну, а как обрабатывать добавление карточек — зависит от реализации.

Реализовать это можно на обычной бинарной куче (priority_queue в C++).

В задаче С надо было записать в граф все ограничения, которые мы имеем из массивов A и B, а именно:
В массиве A:
1. если i < j, A[i] >= A[j], то X[i] > X[j].
2. для каждого A[i] != 1, X[i] больше, чем X[j], где j — номер последнего A[j] == A[i] — 1.

Аналогично для массива B. потом просто осуществить топологическую сортировку в этом графе, при этом, понятное дело, из двух несравнимых вершин раньше идёт та, у которой меньше номер (чтобы последовательность получилась лексикографически минимальной).

Построение хоть какого-то легко доказать (мы каждый раз ничего из "пула" возможных не выкидываем, только добавляем)

Насчет лексикографической минимальности умею убедительно махать руками :)

А так же на 610 и 665, причем двукратные

Вот это уровень, достойный чемпиона мира по программированию — проходить с последнего проходного места.

Слабо?

Если не смотреть в Dashboard'е разбор, то бинарим по ответу и жадно моделируем за количество раундов. Для деталей реализации просто посмотри чужие решения.

Научимся для каждой команды находить, какое максимальное место она может занять. Это означает, что эта команда сначала выигрывает все, что только может, а потом начинает проигрывать. Что означает, что команда выигрывает? Это означает, что среди тех команд, которые до сих пор выступали так же, как она, есть команда, с меньшим номером.

Оk, храним 4 значения: количество команд, которые на сей момент выступили лучше данной количество команд, которые на сей момент выступили хуже данной (с этими командами рассматриваемая команда не поменяется местами уже никогда). количество команд, которые на сей момент выступили так же, как данная, но их номер меньше (они сильнее) количество команд, которые на сей момент выступили хуже данной, но их номер больше (они слабее)

Первоначально эти значения равны 0, 0, k, N — k — 1 (где k — номер рассматриваемой команды)

Дальше прогоняем N раундов. Чтобы подняться как можно выше, команда должна выиграть очередной раунд. Она может это сделать, если последнее значение больше 0. Также желательно, чтобы как можно больше БОЛЕЕ СЛАБЫХ команд, чем рассматриваемая, выступили так же, как она (чтобы потом можно было выигрывать у этих команд). Значит, слабые команды играют друг с другом и выигрывают друг у друга, поэтому последняя величина сокращается в два раза, а проигравшие перемещаются вниз. Аналогично, команды, которые выступили так же, как текущая, но сильнее ее играют друг с другом, проигравшие спускаются вниз.

В итоге получаем лучшее место, которое может занять команда номер k. Похожим образом определяется худшее место, которое может занять команда номер k. Дальше перебираем все команды и для каждой определяем наихудшее и наилучшее место — вот и ответ. Для решения B-large нужно перебор заменить на двоичный поиск по ответу.

Решение за O(1) на тест: http://pastebin.com/aufkpZjV

Использует встроенную в GCC функцию __builtin_clzll, которая (как минимум) на x86 выполняется за константное время. В остальном идеальный C99.

(Решение придумал сам и только сейчас сравнил с официальным. То же самое, хотя в официальном есть недочёт, из-за которого при P = 2^N оно первым числом выводит несуществующий номер команды 2^N + 1 - 2 вместо 2^N - 1. Замечу, что во время контеста я отправил более медленную версию, работающую за O(N), — это я уже поотимизировал.)