Нетрудно убедиться, что самый выгодный для Марио исход каждого из дополнительных заездов — это исход, в котором персонаж v занимает первое место, а персонаж u — последнее. При этом за каждую победу в дополнительном заезде персонаж v будет получать a₁ баллов в общий зачет, а персонаж u будет получать 0 баллов, если k < n, и a_k баллов, если k = n.

Также можно заметить, что в случае, когда b_i = 0, потребуется не более m + 1 дополнительных заездов. Действительно, если сначала в m дополнительных заездах персонаж u займет те же места, что занимал в уже прошедших заездах персонаж v, и наоборот, их общий балл сравняется, так как множества набранных ими баллов будут совпадать. Можно показать, что если в еще одном дополнительном заезде персонаж v займет первое место, а персонаж u — последнее, то общий балл персонажа v станет строго больше общего балла персонажа u.

Подзадачи 1 и 2

Для решения первых двух подзадач достаточно было реализовать систему подсчета общего балла, описанную в условии задачи. До тех пор, пока у персонажа v не больше очков, чем у персонажа u, будем проводить еще один дополнительный заезд и пересчитывать общие баллы этих двух участников. Асимптотика времени работы этого решения составляет O(qm^2s) или , в зависимости от реализации процедуры выбора s минимальных баллов. Баллы за первую подзадачу можно было получить, не реализуя эту процедуру вообще.

Подзадачи 3 и 4

Для решения вторых двух подзадач можно было улучшить решение предыдущих подзадач, заметив, что при добавлении одного дополнительного заезда можно быстро пересчитывать общие баллы персонажей. Для этого достаточно поддерживать сумму всех баллов персонажа, а также множество из s минимальных значений баллов, полученных им. При добавлении нового дополнительного заезда это множество меняется одним из двух возможных способов: если балл персонажа за этот заезд не меньше всех значений, лежащих в этом множестве, то оно не изменяется. В противном случае, из этого множества удаляется максимальный элемент, а вместо него добавляется новый балл. Можно также заметить, что для персонажа v, занимающего всегда первое место, это множество меняться не будет, а для персонажа u, занимающего всегда последнее место, в множество всегда будет добавляться новый результат. Реализовав операции добавления и удаления элемента из множества наивно, за время, пропорциональное размеру множества, получаем решение с асимптотикой времени работы O(qms). Также для решения данных подзадач необходимо было использовать 64-битный тип данных, чтобы избежать переполнения.

Подзадачи 5 и 6

Заметим, что если персонаж v может получить больший общий балл, чем у персонажа u, за некоторое количество дополнительных заездов, то за любое большее количество дополнительных заездов он тоже сможет этого добиться. Значит, для решения данной задачи можно воспользоваться двоичным поиском по ответу. Для его реализации необходимо быстро проверять для любого числа x, верно ли, что персонаж v может получить строго больший общий балл, чем персонаж u, за x дополнительных заездов. Однако в данных подзадачах уже не выполнялось ограничение b_i = 0, а значит, число x может сильно превосходить число m.

Изучим внимательнее, как выглядит множество баллов, набранных персонажем, после x дополнительных раундов. Это множество является объединением множества баллов, набранных им за первые m заездов, и множества, состоящего из x одинаковых значений. Обозначим эти одинаковые значения как y (для персонажа v выполняется y = a₁, а для персонажа u либо y = a_k, либо y = 0). Для того, чтобы получить общий балл, надо из суммы всех элементов этого множества вычесть сумму s минимальных элементов. Сумму всех элементов этого множества можно легко посчитать: она равна сумме баллов, которые получил персонаж за первые m заездов (эта величина постоянная и может быть вычислена один раз в начале программы), увеличенной на xy. Найдем теперь s минимальных элементов в этом множестве. Для того, чтобы это сделать, достаточно заметить, что в число этих элементов могут попасть лишь s минимальных элементов из множества баллов, набранных за первые m заездов, а также число y, которое будет входить в него не более s раз. Значит, можно объединить множество, состоящее из s минимальных баллов за первые m заездов, со множеством, состоящим из s элементов, каждый из которых равен y, и выбрать из получившегося объединения s минимальных элементов. Это можно сделать за время O(s), применив метод двух указателей. Таким образом, можно посчитать общий балл любого персонажа после x дополнительных раундов и применить эту функцию для проверки в двоичном поиске. Асимптотика времени работы всего решения составляет , где C — максимальный возможный ответ. В задаче он не превышает 2·10⁹.