## Editorial for COCI '14 Contest 5 #3 Traktor

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

The goal of this task is to find the first moment when there are exactly mushrooms in a row, column or line parallel to the diagonal.

The solution that was enough for represents the meadow in a matrix and, when adding a new mushroom, checks whether there are exactly mushrooms in a row, column or on the lines where the new mushroom is located.

The solution that was enough for all points remembers for each and coordinate how many mushrooms there are with that or coordinate. Let's observe the lines parallel to the diagonals of the meadow. There are two types of such lines. For the first type, the value of is constant, whereas for the second type the value of is constant and there are such lines for each diagonal. For each such line, we can remember how many mushrooms are located on it.

Now we are only left with finding the first moment when some of the counters get to when a new mushroom is growing.

Total complexity is .