A

Научимся определять расстояние между точками. Далее, зная, что время — это расстояние делить на скорость, будем определять время для каждого таксиста, за которое он сможет доехать до Василия. Ответ это минимальное из времен.Не забудем про double.

Асимптотика O(n).

Решение

B

Пусть c[x] — количество магазинов в которых цена за напиток равна x. Посчитаем для этого массива префиксные суммы. Далее возможные следующие варианты:

1)Если текущее количество денег у Василия больше, чем размер массива с префиксными суммами то выводим n.

2)Иначе выводим префиксную сумму для количества денег, которое сейчас у Василия.

Асимптотика O(q+n).

Решение

C

Будем решать задачу динамическим программированием. dp[i][j] это минимальное количество энергии, которое надо потратить чтобы расположить первые i строк в алфавитном порядке и i-ая из них будет перевернута если j=1 и не перевернута если j=0. dp[i][j] обновляем через dp[i - 1][0] и dp[i - 1][1]. Остается проверить, что i-ая строка лексикографически больше (i - 1)-ой(если j=1 то проверяем перевернутую i-ую строку, аналогично для (i - 1)-ой). После чего обновляем dp[i][j]=min(dp[i][j],dp[i - 1][0]+c[i]*j), dp[i][j]=min(dp[i][j],dp[i - 1][1]+j*c[i]). Ответ это минимум из dp[n][0] и dp[n][1].

Асимптотика O(n+sum_length).

Решение

D

Каждое число из множества будем хранить в двоичной системе счисления(каждое число будет состоять из 32-х 0 или 1) в такой структуре данных как бор(рёбра — это будут биты 1 или 0, а вершины будут отвечать за то, можно ли пройти по текущему ребру). Чтобы ответить на запрос типа "? x" будем спускаться по бору от старших битов к младшим и смотреть можем ли мы сейчас ксором в i-м бите получить единицу, если можем, то переходим, иначе идём туда, куда можем идти.

Асимптотика O(q*log(10^9)).

Решение

E

Обнесем матрицу рамкой из фиктивных элементов. В каждом элементе матрицы и рамки храним значение элемента номер элемента соседнего справа и номер элемента соседнего снизу. Когда приходит запрос поменять местами прямоугольники надо поменять значения элементов только по периметру прямоугольников.

Асимптотика O(q*(n+m)).

Решение