SPOOL Editorial

deadwing97 · August 30, 2018, 1:44am

PROBLEM LINK:

Author: Hasan Jaddouh
Tester: Hussain Kara Fallah
Editorialist: Hussain Kara Fallah

PROBLEM

Chef has a swimming pool. The swimming pool is N metres in length (long course) and a fixed width 1 metre. Its long course is split into N equal parts, with possibly different depths. For each valid i, the i-th part has depth D_i metres.

You should process Q queries. There are two types of queries:

1 x v pour v cubic metres of water into the x_th part of the pool
2 x find how much metres deep is the water surface from the ground in the x_th part of the pool.

Water level obeys the following rules. As long as the water level in some part of the pool is higher than the water level in at least one of the adjacent parts, the water from it will move to adjacent parts with lower water levels until water levels become equal or there is no water left in this part. If the adjacent part from both sides (left and right) have lower water level then the half of the quantity of water in the current part will move to left and the other half will move to the right. The water on the leftmost part can’t move to the left, and the water on the rightmost part can’t move to the right.

When the water level reaches the surface of the pool (i.e. its depth become 0), the pool overflows and the water level does not increase anymore.

Please refer to the problem samples for better understanding.

PREREQUISTES:

Disjoint sets

CONSTRAINTS

N,Q <= 10⁵

DIFFICULTY

HARD

EXPLANATION

Suppose we poured water on the x_th part of the pool. Think where the water would go.

Let’s suppose that the water will move to the left. Where will it stop?

It will stop at the A_th part which is the first part the satisfies:

D_i >= D_i+1 for each i in range [y,x-1]
D_y >= D_y-1 (if y > 1)

Let’s put it in words (should be the first part such that the parts starting from the x_th one till the y_th forms a non-decreasing sequence AND the y_th part is deeper than the part to its left.

By the same logic we can deduce the position of the part that the water will stop at while moving right. (of course it will not stop forever there, because after filling these parts the water may continue flowing BUT at least some water will residue there.

Let’s suppose that at each query we could know these parts quickly (just assume that). Solving the problem would be easy. After figuring the part that water will residue at (from the left side and right side). The water would keep residing there (in half) until one of these parts become on the same level with the one to its left or to its right (after that the water will behave differently).

IMPORTANT OBSERVATION

Whenever a part of our pool becomes on the same level with one of its adjacent neighbor parts we can treat them as the same part with the same level and their levels must keep growing together (till the pool overflows). So we will have at most n-1 merges. This will allow us to use the disjoint set union.

So now for each pouring query, we can figure out where the water will stop from left and from the right. We can also determine the amount of water that will move until the current scenario changes (one of these 2 parts become on the same level with one of its neighbors). We keep pouring water until that moment and after that merge the parts that became on the same level. After that, we can call the function recursively to continue pouring (Since there will be no more that n-1 merges it will be ok).
I will not explain how to handle cases of pouring water (left finish first, right finish first, none is finished…) because it’s not hard to come with.

Now we should think what we should keep for each disjoint-set union structure. Since we merge neighboring parts with the same level we should keep the leftmost part and the rightmost part in each union. Of course along with the level of this union.

We still need to know one more thing, how to get the parts that water will stop at quickly?

We just need to maintain 2 sets. The first set contains the indices of parts such that each part is deeper than the part on its right. The second set contains the indices of parts such that each part is deeper than the part on its left.

So when pouring on some part just find the nearest one to its right deeper than its right neighbor and the same for the left. When some part has its level increased we can just delete it from one of the sets (or both) if necessary.

Complexity

O(n log n)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s/Editorialist’s solution can be found here.