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)).
