567A - Lineland Mail

Let's sort all the cities by x coordinate (saving its numbers for later). Consider all indexes below in this sorted order.

One can notice that the maximum cost of sending a letter from i'th city is equal to maximum of distances from i'th city to first city and from i'th city to last (max(abs(x_i - x₀), abs(x_i - x_n - 1)). On the other hand, the minimum cost of sending a letter will be the minimum of distances between neighboring cities (i - 1'th and i + 1'th cities), more formally, min(abs(x_i - x_i - 1), abs(x_i - x_i + 1). For each city, except the first and the last this formula is correct, but for them formulas are (abs(x_i - x_i + 1)) and (abs(x_i - x_i - 1)) respectively.

567B - Berland National Library

To answer the queries correct, we need to know if the person is still in the library. For that purpose we will use in array of type bool. Also we will store two variables for the answer and ''current state'' (it will store the current number of people in the library). Let's call them ans and state respectively.

Thus, if we are given query  + a_i then we should increase state by one, mark that this person entered the library (in[a_i] = true) and try to update the answer (ans = max(ans, state)).

Otherwise we are given  - a_i query. If the person who leaves the library, was in there, we should just decrease state by one. Otherwise, if this person was not in the library (in[a_i] == false) and leaves now, he entered the library before we started counting. It means we should increase the answer by one anyway. Also one should not forget that it is needed to mark that the person has left the library (in[a_i] = false).

567C - Geometric Progression

Let's solve this problem for fixed middle element of progression. This means that if we fix element a_i then the progression must consist of a_i / k and a_i·k elements. It could not be possible, for example, if a_i is not divisible by k ().

For fixed middle element one could find the number of sequences by counting how many a_i / k elements are placed left from fixed element and how many a_i·k are placed right from it, and then multiplying this numbers. To do this, one could use two associative arrays A_l and A_r, where for each key x will be stored count of occurences of x placed left (or right respectively) from current element. This could be done with map structure.

Sum of values calculated as described above will give the answer to the problem.

567D - One-Dimensional Battle Ships

Editorial to this task will be posted later.

567E - President and Roads

Editorial to this task will be posted later.

567F - Mausoleum

Editorial to this task will be posted later.