Firstly, we will describe a naive approach. We could, for example, first draw the painted image. In other words, fill the skyscrapers' area with #. After filling that out, the image from the first example from the task would look like this:

........####
####....####
####..######
####..######
####..######
************

Now we are left with whiting out the interior of the skyscrapers. Notice that the character # becomes . only if none of the surrounding characters (in all ~8~ directions) is .. By implementing this algorithm, we get the wanted image.

The perimeter can be calculated from the given image by carefully counting the characters #. First, let us add to the perimeter all the characters #. Notice that some of the characters # participate in building two sides, whereas some of them don't participate at all. The perimeter should be increased by the number of characters participating in two sides and decreased by the number of characters participating in none. The characters being added to the perimeter are marked with red and the ones being subtracted are marked with blue:

........####
####....#..#
#..#..###..#
#..#..#....#
#..#..#....#
************

It is clear that the characters that are being added are in fact the upper corners of the skyscrapers and are of the shape:

##      ##
#.  or  .#

whereas the characters being subtracted are the points of contact between two skyscrapers and are of the shape:

.#      #.
##  or  ##

Solutions such as this, their the complexity being ~\mathcal O(\text{sum_of_areas})~, were enough to get ~50\%~ of total points.

Let ~maxh[i]~ denote the maximum height of a skyscraper that stretches over the ~i^\text{th}~ column. The elements of this array can be calculated in the complexity ~\mathcal O(N \times (\max R_i - \min L_i))~.

Calculating the perimeter comes down to linearly iterating over the array ~maxh~ where we add to the final solution the absolute difference between the adjacent elements (two vertical sides) and one for each column where ~maxh[i] > 0~ (horizontal sides). A similar procedure is used to reconstruct the image. This implementation was sufficient for all points.