We can interpret the number of islands as the number of connected components in the graph formed by pieces of land being nodes and edges existing between two adjacent pieces of land if and only if both of them are above water (elevations greater than or equal to sea level ~s~).

Subtask 1

There are various solutions to subtask 1, but we will present one which easily evolves into idea for subtask 2.

Consider reversing the process and sweeping the sea level ~s~ from ~N+1~ down to ~1~. This can be interpreted as beginning with DMOJistan fully submerged underwater, and as the sea level ~s~ decreases, the ~i^{th}~ patch of land is "inserted" when ~s = h_i~.

To maintain the number of distinct islands with this interpretation, we consider the three cases when "inserting" a patch of land:

1. Both of the patches of land adjacent to this patch of land are still submerged (i.e. not yet "inserted").

   • In this case, a new island is created. Total number of islands increases by ~1~.

2. One of the patches of land adjacent to this patch of land is already above water (i.e. already "inserted").

   • In this case, the new patch of land becomes connected to an existing island, and no new islands are created. Total number of islands does not change.

3. Both of the patches of land adjacent to this patch of land are above water (i.e. already "inserted").

   • In this case, the new patch of land merges the two islands next to it into one, resulting in only one island. Total number of islands decreases by ~1~.

Thus, we can maintain the total number of islands in DMOJistan by initializing it to ~0~, keeping track of which patches of land have been inserted using a boolean array and sweeping the land insert events from ~N~ down to ~1~. Ensure that all patches of land with elevation ~i~ and above are inserted before storing the number of islands ~c_i~ as the answer.

Preprocessing the order of the events can be done in ~\mathcal{O}(N \log N)~ time by sorting the patches of land from highest elevation to lowest or in ~\mathcal{O}(N)~ time by placing the patches of land into ~N~ buckets. The calculation itself takes ~\mathcal{O}(N)~ time.

Time Complexity: ~\mathcal{O}(N)~ or ~\mathcal{O}(N \log N)~

Subtask 2

In this subtask, we need to construct the events from Subtask 1 such that they create the given sequence of island quantities. Intuitively, we should also try to minimize the number of events we use so that we do not run out of patches of land. As a result, we should only ever use events to increase the number of islands or decrease the number of islands (i.e. we should never use a Case 2 insertion as described in Subtask 1).

Again, we work backwards with the sea level ~s~ dropping from ~N+1~ to ~1~. Let ~c_{N+1} = 0~.

When transitioning from sea level ~i+1~ to sea level ~i~, there are once again three cases:

1. Total number of islands does not change, ~c_i = c_{i+1}~.

   • In this case, we can simply avoid making any patches of land with elevation ~i~ so that no events occur at this sea level and the number of islands stays the same.

2. Total number of islands increases ~c_i > c_{i+1}~.

   • In this case, we need to add ~c_i - c_{i+1}~ new islands.
   • To minimize the number of patches of land required to do this, we can make exactly ~c_i - c_{i+1}~ isolated patches of land have elevations equal to ~i~, spaced apart by single patches of currently submerged land (any land not yet assigned an elevation).
   • Effectively, we are reserving patches of land at odd indices for creating new islands.
   • If we ever run out of patches of land to create new islands, then a construction does not exist -> break and output -1.

3. Total number of islands decreases ~c_i < c_{i+1}~.

   • In this case, we need to perform ~c_{i+1} - c_i~ merges.
   • To do this, we can fill in the gaps created by the spaced apart islands in case ~2~, setting the elevation of exactly ~c_{i+1} - c_i~ patches of land which are in between two previously inserted patches of land to be ~i~.
   • Effectively, we are reserving patches of land at even indices for merging islands.
   • If we ever run out of gaps where we can merge two adjacent islands, then a construction does not exist -> break and output -1.

After, if any patches of land still have unassigned elevations, simply set them to ~0~.

Time Complexity: ~\mathcal{O}(N)~

Bonus

Author Commentary

Bruh why are there like 999999999 solutions to this problem...

I see intended solutions, dsu solutions, difference array solutions, segment tree solutions, and some small to large vector merging thingy from icecreammmm???

Anyway, nice problem, one of my better ones. In my opinion it's fairly approachable even for people who are not too experienced in competitive programming, because the (intended) solutions may be hard to find, but are simple conceptually.