A
We know that time=distance/speed. For each car we should find timei, than if it is less than answer we should update it.
Time Complexity: O(n).
B
Consider c[x] the number of stores in which the price per drink is x. We calculate this array prefix sum. Then the following options: 1) If the current amount of money m is larger than the size of the array with the prefix sums than answer is $n4. 2) Otherwise, the answer is c[m].
Time Complexity: O(n+q).
C
We will solve the problem with the help of dynamic programming. dp[i][j] is the minimum amount of energy that should be spent to make first i strings sorted in lexicographical order and i-th of them will be reversed if j = 1 and not reversed if j = 0. dp[i][j] is updated by dp[i-1][0] and dp[i-1][1]. It remains to verify that the i-th string is lexicographically greater than (i-1)th (if j = 1 then we should check reversed i-th string, similar to (i-1)-th). Then we update 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]). The answer is a minimum of dp[n][0] and dp[n][1].
Time Complexity: O(n+sum_length).
D
Let's store each number in binary system (each number consists of 32 bits, 0 or 1) in such a data structure as trie.The edges will be the bits 1 and 0, and the vertices will be responsible for whether it is possible to pass the current edge. To reply to a query like "? X" will descend the forest of high-order bits to whether the younger and now we can look RRF in the i-th bit to get one, if we can, then move on, otherwise we go to where we can go.
Time Complexity: O(q*log(10^9)).
E
Обнесем матрицу рамкой из фиктивных элементов. В каждом элементе матрицы и рамки храним значение элемента номер элемента соседнего справа и номер элемента соседнего слева. Когда приходит запрос поменять местами прямоугольники надо поменять значения элементов только по периметру прямоугольников.
Асимптотика O(q*(n+m)).
