ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1987. Nested Segments

Help me
Posted by Unsocial_A 19 Sep 2018 22:34
How can I solve this problem by using segment tree??
Re: Help me
Posted by Didi (OSU11) 15 Oct 2018 17:14
It was uneasy, but I did it! 3 days of thinking left. I use array of ranges. Each range is both-direction (parent-child) tree. I crossed the input 3 times (for read data, for evaluate a length of each subnode, for build array of ranges.
I had such problems, such as TLE (I solved it with refusing of lists, I use child array[10^5] for each node). I get MLE-Memory limit exception (It solved with evaluate of node length O(n). it was hard!).
The tree was a genious idea! But I had TLE, becouse I ran from 0 to ChildArr.Length everytime. I need in dynamically an BeginChildId for each parent. TLE went away from my eyes!
4 cycle has Mx(crossing the ranges) complexity. I used a PrevOtr object. 1 query could to have 1 or 2 ranges (begin of 2 range, so keep in mind! You must understand that).
That is part of FindNode function  code:
...
do
{
prv = null;
for (int i = inner.BegChild; i < inner.ChildN//inner.Childs.Count()
; i++)
if (query >= inner.Childs[i].X && query <= inner.Childs[i].Y)
{
prv = inner.Childs[i];
inner.BegChild = i;
break;
}
if (prv != null)
inner = prv;
}
while (prv != null);
...

Edited by author 15.10.2018 17:15