ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1987. Nested Segments

Accepted 0.483 sec, 6992Kb
Posted by nadinne 9 Feb 2016 14:52
I used scanline to solve this problem. This method is shown
here: http://e-maxx.ru/algo/length_of_segments_union. All the given points are put in array with 2n+m elements, each point having one of 3 types: start of a segment(0), end of a segment(2), a point for which the answer is needed (1). Then the array is sorted, and we go througth its elements: if the element has type 0, then we insert according segment into the set, if the element has type 2, then we delete according segment from the set, if the element has type 1 then we take the segment of minimum length from set in O(1), and output its id. The complexity is O((2n+m)log(2n+m)) (quicksort).

Edited by author 09.02.2016 14:53
Re: Accepted 0.483 sec, 6992Kb
Posted by Saket Patel 29 May 2017 14:15
Stack can be used in place of set, reducing time to about 0.148 sec

Edited by author 29.05.2017 14:16