hackercupai/hackercup huggingface dataset:
We'll process the rectangles one by one while computing \(P_{1..N}\). When processing the \(i\)th rectangle, we can't afford to compute the perimeter of the union of the first \(i\) rectangles from scratch (as this would result in an inefficient algorithm with time complexity at least \(O(N^2)\)), so we'll instead compute how the inclusion of this rectangle affects the existing rectangle union (and therefore how \(P_i\) differs from \(P_{i-1}\), assuming that \(P_0 = 0\)).

If the \(i\)th rectangle does not overlap (inclusively) with any existing rectangles (in other words, if either \(i = 1\) or \(L_i > L_{i-1} + W\)), then its entire perimeter will be added to the union's perimeter: \(P_i = P_{i-1} + 2(W + H_i)\).

Otherwise, let's separately consider the amount of horizontal and vertical perimeter added. The amount of additional horizontal perimeter is simply the amount of extra width that the union's perimeter spans, multiplied by two (to account for both the top and the bottom): \(2(L_i - L_{i-1})\). Meanwhile, the amount of additional vertical perimeter is dependent on the largest height \(h\) of any existing rectangle which the \(i\)th one overlaps (inclusively) with. Specifically, if \(H_i \le h\), then there is no additional vertical perimeter (as the top of the union still only comes down from \(h\) to \(0\)), while there will otherwise be \(2(H_i - h)\) additional vertical perimeter (as the top of the union goes up to a height of \(H_i\) and then back down).

The simplest way to compute \(h\) in the above expression is to loop back over all of the rectangles overlapping with the \(i\)th one, which are at most the last \(W\) ones. This approach results in a time complexity of \(O(NW)\), which is sufficient.

However, it can also be optimized down to just \(O(N)\) by maintaining a deque of rectangles which could possibly be relevant for this purpose in the future (that is, ones whose \(L\) values are no less than \(L_i - W\), and which have both increasing \(L\) values and decreasing \(H\) values). The rectangle with the largest height overlapping with the \(i\)th one is then known to be the earliest one in this deque.