Complexity Analysis

general
1

Hello guys,

I was giving a contest on Codeforces recently.I could not solve one problem on it so I was looking into the editorial of it afterwards.But since the editorial was quite brief so I am not able to understand their solution and its complexity especially the solution using priority queue. So I request you to please help me.

Question: [Problem Statement][1]

Editorial: [Editorial][2]

Thanks.
[1]: Problem - C - Codeforces
[2]: Codeforces Round #296 Editorial - Codeforces

2

Let’s solve task independently for vertical and horizontal cuts; at every moment you have some set of segments, and you are interested in length of longest among them. To make a cut, you should also store set of cuts you already did. Knowing that cuts and the cut from query, you can find a segment you are cutting in logarithmic time (using some lower_bound etc.). So you just throw away that segment and add two new segments instead.

3

See the basic approach to solve this question is the find the maximum horizontal and vertical line segments after all the cuts.

So to implement the above algorithm maintain two sets that store the line segments.

set x;

set y;

Place all the line segments parallel to the x-axis in x and parallel to y in set y.

So, x.insert(0);

x.insert(w);

and
y.insert(0);

y.insert(h);

After performing the cuts if the cut is a horizontal one, then you can easily see that there will be no effect on the horizontal lines whereas the vertical line segment will get cut short. Find the line segment that is just bigger than the performed cut and the line segment that is just smaller than the cut.

Lets call them l2 and l1 and the current cut as l.

So insert in the set y -> l2-l and l-l1.

Also maintain another multiset (because it can contain duplicate values) that stores the length of the line segments. Insert the two new lengths and delete the length l1+l2 from it.

Similarly do the process for the ‘V’ cut.

Hope you understand this well :slight_smile: .