Let us examine a part of the city between a pair of buildings and mark it with ~[X, Y]~. To begin with, we do not care about the transmitters to the right of that interval. Every transmitter covers a part ~[Z, Y]~, while the left part ~[X, Z]~ stays uncovered. It is sufficient to find a transmitter with the minimal ~Z~, let's call it ~Z_L~.

We conclude similarly for the transmitters to the right of that interval. Then the part ~[X, Z]~ is going to be covered, and the part ~[Z, Y]~ uncovered. Here we need to find the transmitter with the maximal ~Z~, let's call it ~Z_D~.

When we find these two coordinates, ~Z_L~ and ~Z_D~, for an interval ~[X, Y]~, we can calculate the coverage of an interval as: ~Y-X-\max\{0, Z_L-Z_D\}~. The task is now unfolded into two parts: the first will calculate ~Z_L~ for every interval, and the second ~Z_D~ in a similar way.

Now we will explain how to calculate ~Z_L~. We can notice that for every transmitter it is sufficient to observe only the part of signal located to the right of it.

We will sweep through all the buildings from left to right. By doing so, we will maintain a structure which will contain some of the transmitters from the buildings we have already swept through. The transmitters in the structure will be sorted in ascending order according to their abscissa. In the structure, each transmitter is paired with a point on the ~X~ axis which marks the place where the coverage of that transmitter begins, if we take into account the buildings we have swept so far (the coverage extends from that point to the right).

Now we will demonstrate an important property of this structure. For a transmitter ~O~, we mark ~X_O~ as its abscissa, ~H_O~ as its height and ~T_O~ as its paired point, more specifically the abscissa of that point. Let us also define the predicate better. For a pair of transmitters ~A~ and ~B~, we say that ~A~ is better than ~B~ if ~T_A < T_B~. Let us assume that there are two transmitters in the structure: ~A~ and ~B~, with ~X_A < X_B~ being true. If ~H_A \le H_B~ is true, transmitter ~B~ can be left out because ~A~ is better. Let us assume, therefore, additionally that ~H_A > H_B~ is true. If ~T_A < T_B~, transmitter ~B~ can be left out, because ~A~ will always be better.

Taking this property into consideration, we are left with the following consequences: the heights of the transmitters in the structure are going to be descending and the abscissa of the paired points are going to be ascending.

Now we can easily come up with an algorithm which is applied to each building we come across (while sweeping through them from left to right). Initially, we leave out all transmitters from the end of the structure which are of equal or lower height than the current building. If the current building has a transmitter on it, we add it to the structure and ~Z_L~ for this interval is equal to ~X~ (the abscissa of the current building's transmitter). If the current building doesn't have a transmitter, we observe the last two transmitters in the structure. Now we update their paired points (maybe they will be changed after the addition of the last building). If, after the update, the last transmitter doesn't comply with the structure's property (~T_A > T_B~, where ~A~ is the second-to-last, and ~B~ the last transmitter in the structure), we leave it out of the structure. This procedure is repeated while possible (in other words, until the last transmitter complies with the structure's property) while always updating the paired point of the second-to-last transmitter.

We can notice that we won't need to update the paired points of the other transmitters in the structure after we've finished this procedure for a building because they do not change. Let us assume the contrary, we have two transmitters: ~A~ and ~B~, ~X_A < X_B~, ~H_A > H_B~ and ~T_A \ge T_B~, and ~A~ needs to be updated and ~B~ does not. We construct a line ~P_A~ through points ~(X_A, H_A)~ and ~(T_A, 0)~ and a line ~P_B~ through points ~(X_B, H_B)~ and ~(T_B, 0)~. The last condition means that the current wall intersects with ~P_A~ and doesn't intersect with ~P_B~. However, that is impossible because then ~B~ would not comply with the structure's property. More specifically, the condition ~T_A \ge T_B~ would not be met.

When we sweep through all buildings from left to right, a very similar procedure is repeated in the same way on the opposite side and this gives us arrays ZL and ZD from which we construct the final solution.

In this task's solution, we sweep through all buildings twice, maintaining the structure which can be implemented as a stack. Every step of going through the buildings is of constant complexity because when sweeping through all buildings, we insert and leave out each transmitter exactly once. Given the fact that all the structure's operations are of linear complexity, the final solution's complexity is also linear, ~\mathcal O(N)~.