Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Help needed in MINMAGIC Codechef

Revision en1, by rhezo, 2016-10-07 04:10:21

Hi, I need some help in MINMAGIC problem on Codechef.

The problem statement in short: There are N segments, and Q queries. Each query is of the form (A, B). For each segment we need to choose a point on it, say X and find min(abs(A - X), abs(B - X)). We need to add this minvalue for all such segments and report the answer.

What I did: It is easy to find the answer for all segments whose right end point is less than A and whose left end point is greater than B. The minvalue is 0 for intervals that contain either A or B.

So the problem essentially boils down to this: Given 2 points (A, B) and some N segments all between A and B. For each segment we either choose its left end point or right end point and find the minvalue as above and add it for all the segments.

I don't know how to do this part. I am also not able to understand this solution by I_love_Tanya_Romanova. Also this solution is very clean but still can't understand the last part.

Can anyone help me in this? There are also some solutions by Treaps, I would appreciate if anyone can elaborate on that too.

History

Revisions

Rev. Lang. By When Δ Comment
en1 rhezo 2016-10-07 04:10:21 1335 Initial revision (published)