485A - Factory

Production will stops iff exists integer K ≥ 0 such a·2^K is divisible by m. From this fact follows that K maximum will be about O(log₂(m)). So if we modeling some, for example, 20 days and production does not stop, then it will never stop and answer is "No". Otherwise answer is "Yes".

485B - Valuable Resources

Let us find minimum length needed to cover points by Ox. It is Maximum(x_i) - Minumum(x_i). The same in Oy — Maximum(y_i) - Minumum(y_i). Since we need a square city to cover all the mines, then we need to set length of this square to the maximum from those two values.

484A - Bits

Let us define function f(L, R), that gives answer to the query. It looks follows:

• if L = R then f(L, R) = L;

• else if 2^b ≤ L, where b — maximum integer such 2^b ≤ R, then f(L, R) = f(L - 2^b, R - 2^b) + 2^b;

• else if 2^b + 1 - 1 ≤ R then f(L, R) = 2^b + 1 - 1;

• else f(L, R) = 2^b - 1.

Total complexity is O(logR) per query.

484B - Maximum Value

Let us iterate over all different a_j. Since we need to maximize , then iterate all integer x (such x divisible by a_j) in range from 2a_j to M, where M — doubled maximum value of the sequence. For each such x we need to find maximum a_i, such a_i < x. Limits for numbers allow to do this in time O(1) with an array. After that, update answer by value . Total time complexity is O(nlogn + MlogM).

484C - Strange Sorting

Note, that d-sorting is just a permutation (call it P), because it does not depends on characters in string. Look at shuffling operation in different way: instead of going to the next substring and sort it, we will shift string to one character left. It remains to understand that shift of string the permutation too (call it C). Now its clear, we need to calculate S·P·C·P·C... = S·(P·C)^{n - k + 1}. And after that shift string for k - 1 character to the left for making answer to the shuffling operation. Here we use the multiplication of permutations. Since they are associative, that we can use binary algorithm to calculate (P·C)^{n - k + 1}. Total time complexity is O(nmlogn).

484D - Kindergarten

Let us note, that in optimal answer any segment that making a group contains their minimum and maximum values on borders. Otherwise it will be better to split this segment to two other segments. Another note that is every segment in optimal solution is strictly monotonic (increasing or decreasing). Paying attention to the interesting points in sequence which making local maximums (i. e. a_i - 1 < a_i > a_i + 1), local minimums (a_i - 1 > a_i < a_i + 1), and point adjacent to them. Solve the problem by dynamic programming: D_i is the answer in the prefix i. To calculate D_i we need to look at no more than three previous interesting points and to previous D_i - 1. Total time complexity is O(n).

484E - Sign on Fence

Let us note that we can use binary search to find answer to the one query. Suppose at some moment was fixed height h and need to know will fit the rectangle with width w and height h to the segment of fence from l-th to r-th panel. Let us build data structure that can answer to this question. This will be persistent segment tree with unusual function inside: maximum number of consecutive ones in segment (maxOnes). In leaves of segment tree will be only numbers 0 and 1. To calculate this function need to know some other values, specifically:

len — length of the segment in vertex of segment tree, prefOnes — length of prefix that consists only of ones, sufOnes — length of the suffix consist only of ones.

These functions are computed as follows:

maxOnes is equal to max(maxOnes(Left), maxOnes(Right), sufOnes(Left) + prefOnes(Right));

prefOnes equals prefOnes(Right) + len(Left) in case of len(Left) = prefOnes(Left), and prefOnes(Left) otherwise;

sufOnes equals sufOnes(Left) + len(Right) in case of len(Right) = sufOnes(Right), and sufOnes(Right) otherwise;

len = len(left) + len(Right);

Left и Right — it is left and right sons of vertex in segment tree.

As mentioned above, tree must be persistent, and it must be built as follows. First, builded empty tree of zeros. Next in position of highest plank need to put 1. The same doing for planks in decreasing order. For example if fence described with sequence [2, 5, 5, 1, 3] then bottom of segment tree will changed as follows:

[0, 0, 0, 0, 0] -> [0, 1, 0, 0, 0] -> [0, 1, 1, 0, 0] -> [0, 1, 1, 0, 1] -> [1, 1, 1, 0, 1] -> [1, 1, 1, 1, 1].

And we need to remember for all h_i their version of tree. Now to answer the question we need to make query in our segment tree (that corresponding to height h) on segment [l, r]. If maxOnes form this query less than w, then rectangle impossible to put (otherwise possible).

Building of tree will take O(nlogn) time and memory. Time complexity to the one query will take O(log²n) time.