In this question, the editorial solves the question with formula max(L+h1,a[w2]). I don’t get it how did he reach the conclusion. And also the problem set has a tag of the data structure. Which data structure should be used here?
I’ll try to explain how to reach the formula.
Lets solve a very easy version of the problem first i.e. suppose a box gets destroyed before the next box arrives. So whenever a box arrives, there are no other boxes on the staircase. Now, suppose you have to answer the same query for a box with width w_{i}. The answer for this query would simply be a[w_{i}]\ . Why? Since our box has width w_{i}\ , it spans from the complete left to the w_{i}'th stair, thus the answer should be the largest height between indices 1 and w_{i} (considering 1 based indexing). Also, we know that a represents a staircase, increasing from left to right i.e. array a is in non-decreasing order, so the stair having maximum height between indices 1 and w_{i} should be the w_{i}'th stair. Thus the answer in this case is simply a[w_{i}].
Keeping in mind the easier case, lets come back to the original problem. Now older boxes are not destroyed. Suppose the first box to fall has height h_{1} and width w_{1} and the second box to fall has height h_{2} and width w_{2}. The answer for the first box will be a[w_{1}] since this is similar to the easier case we discussed earlier as this is the first box. Let this answer (for the first box) be L ( = a[w_{1}]). Now, the answer for the second box may be affected by the first box. If the first box was destroyed, the answer for the second box would be a[w_{2}]. But what happens if the top of the first box reaches a height greater that the height of the w_2'th stair. If this happens then the second box will collide with the first box before the w_2'th stair and remain there. So the answer for the second box = max(height\ of\ the\ top\ of\ the\ previous\ box,\ a[w_{2}]) = max(L+h_{1},\ a[w_{2}]).
This problem could be solved without any special data structure because all the boxes always begin at the first staircase i.e. on the extreme left. You would need something like a segment tree to solve the case where the starting position of the boxes is also specified.
I hope I was clear enough.
Do have a look at the picture given in the problem statement for a better understanding of the cases we discussed.
2 Likes