79A - Игра в автобусе

We can directly simulate the process and thus obtain the final result.

79B - Разноцветное поле

We store the positions of all the “waste” in each row, and also the corresponding number. For each query, we find the right row and check whether it is “waste” or not. If no, then we calculate the total number of waste before this position, which can be obtained with constant complexity if we use prefix technique. Then, we will know the total number of crops and the correct type can be computed according to the remainder obtained by dividing 3.

79C - Скучные строки

For each of the given n small strings, we can calculate its beginning and ending positions in the long string, where it appears. The above results can be directly computed without using any advanced techniques about string, since the length of small string is quite short.

For each index i in the long string, we store two types of information. We first record the indices of small strings that start from i and their beginning position, specifically in this trival case equal to i. Secondly, we record the indicies of small strings that end at i and their beginning position, which is just i - length(smallstring) + 1.

The left work is to use two pointers technique to calculate the required answer. We use p1 and p2 to denote the beginning and ending positions of the current range that we are observing. At the same time, we record a “set” which contains the small strings belonging to the current range.

When we move p2 forward by one step, we add new small strings (if any) to the set, and check is there any small string ending at p2 are included in the set. If yes, it means that the current range contains at least one small string and thus we should move p1 forward by one step to obtain a new range for the next check. Before p1 is increased, all the small strings that start at p1 should be deleted from the set. If no, we can further move p2 forward to check the next extended range.

As we use “set” in the STL of C++, the updating of set has complexity of O(logN), and thus the total complexity is O(NlogN).