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

Posted by Denis Rozimovschii 14 Aug 2015 22:02
One of the solutions would involve sorting and stacks. I've tried to use reb-black tree, but it seems to have problems with dublicate-keys.

Edited by author 14.08.2015 22:05
Re: Solution
Posted by Timo 21 Aug 2015 03:54
I got AC by iterating all the ranges and putting them in a stack. Basically, if next range fits into previous one, put it in a stack. If it does not, remove previous ranges from the stack until it does (or the stack gets empty).
At each step, update the answers to relevant queries. Binary search is good enough for finding them.
Re: Solution
Posted by ketovdk 29 Mar 2018 23:24
it's possible to solve this problem with segment tree. Just put all answers into segment tree with meaning -1 and then update it with segments, sorted by range