Show all threads Hide all threads Show all messages Hide all messages |
If you sort segments according to INCREASING length | Mahilewets | 1987. Nested Segments | 13 Apr 2023 23:54 | 2 |
If you sort segments according to INCREASING length. Then you can consider all segments one by one consecutively. Find points belong to the current segment. For those points current segment is the answer. Because of the segments are sorted. From all suggested hints, this is the fastest way to do it. Initially I tried with trees, but I was getting TLE on #13. Finally I decided to use a map for the points (with key=point, value=index) It's a very convenient Data Structure, because it provides fast search for the nearest value (lower bound), and allows you to delete that point once its segment has been found. I tried without deleting it, but got TLE #14. Deleting each point from the map after finding it makes the map smaller after each iteration. Finally got an AC in 0.1 |
wa5 | >>> | 1987. Nested Segments | 2 Jul 2022 22:06 | 1 |
i dont have any idea why wa5.. Edited by author 02.07.2022 22:06 |
Good problem. | silverfox | 1987. Nested Segments | 17 May 2022 11:31 | 1 |
Sort the intervals by length. and from i=0 to no_of_intervals, mark the query numbers. Make sure that each query number is marked by only one interval. Edited by author 17.05.2022 11:32 |
why wa10? | Felix_Mate | 1987. Nested Segments | 20 May 2020 23:29 | 4 |
I found my mistake. Helpfull test: 4 1 2 3 100 4 5 6 7 2 1 7 ans: 1 4 HINT:This problem can be solved O(n) with stack. Edited by author 31.08.2016 10:07 Try to use 'longint' instead of 'int64'. In some problems it helps if you have WA. Thank you so much for the test! |
If you have WA5 | SButterfly [Samara SAU] | 1987. Nested Segments | 5 Jan 2020 19:55 | 3 |
Try this test: 5 2 10 2 4 3 4 6 9 7 8 11 1 2 3 4 5 6 7 8 9 10 11 Answer: -1 2 3 3 1 4 5 5 4 1 -1 Try this test: 5 2 10 2 4 3 4 6 9 7 8 11 1 2 3 4 5 6 7 8 9 10 11 Answer: -1 2 3 3 1 4 5 5 4 1 -1 My code passes this test... Still getting WA5. The following test helped me to get AC: 7 2 8 2 6 3 3 6 6 7 7 8 8 9 10 10 1 2 3 4 5 6 7 8 9 10 Answer: -1 2 3 2 2 4 5 6 7 7 I used points sorting + stack approach. My error was in sorting function: I didn't handle situation when points have the same coordinates, the same types, but belong to different segments. Once I added condition which deals with segment numbers, I got AC. By the way, different compilers may give different results: my program compiled with visual studio gave correct results, while g++ did not. Edited by author 05.01.2020 20:01 |
Help me | Unsocial_A | 1987. Nested Segments | 15 Oct 2018 17:14 | 2 |
Help me Unsocial_A 19 Sep 2018 22:34 How can I solve this problem by using segment tree?? 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 |
Solution | Denis Rozimovschii | 1987. Nested Segments | 29 Mar 2018 23:24 | 3 |
Solution 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 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. 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 |
Runtime error - Test 2 | Valentina | 1987. Nested Segments | 31 Jan 2018 23:23 | 1 |
I've got Runtime error in Test 2. I've written the code in Java. Could anybody share the test case for the Test2? |
Accepted 0.483 sec, 6992Kb | nadinne | 1987. Nested Segments | 29 May 2017 14:15 | 2 |
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:53Stack can be used in place of set, reducing time to about 0.148 sec Edited by author 29.05.2017 14:16 |
Test 24 | fallennoir | 1987. Nested Segments | 21 Aug 2015 00:08 | 2 |
Test 24 fallennoir 3 Nov 2013 17:49 TLE24 with 3 different codes <3 |
Clarity for Problem Statement | Jihan Yin | 1987. Nested Segments | 6 Jan 2015 22:49 | 2 |
My code got WA for #27. After checking forever for errors, I edited my comparison for my set so that if two distances are equal, the distance with the bigger key will come first as a last desperation. After submitting this, I got AC. I think this should be stated in the problem statement, because it affects the solutions. For those that don't understand what I'm talking about: Input: 2 1 1 1 1 1 1 (Before) WA 27 Output: 1 (After) AC Output: 2 Your sample is incorrect. Because in the statment: "The segments are ordered by non-decreasing ai, and when ai = aj they are ordered by decreasing length. All segments are distinct." |
i'm sad | Two-Eight-Nine [[ §289]] | 1987. Nested Segments | 24 Apr 2014 04:06 | 9 |
i'm sad Two-Eight-Nine [[ §289]] 2 Jan 2014 15:27 Algo O(nm) works for 1.046 sec, but O(2n) uses more than 65536kb. Edited by author 02.01.2014 15:28 Re: i'm sad Evgeniy_Chernobrovkin(MUCTR-2013) 21 Jan 2014 06:15 1.031 for O(NxM) with pre-exit after left coordinate of segment > coordinate of point. Any idea for modifications? 0.625 for O(mlogn) solution using C++ STL set... I think the problem is harder, than its difficulty score if there is no easier solution. Well, okay, there is a O(mlogn) solution with sorting only and 0.125s execution time. Can you please write some more details for sorting based algorithm? I think you can search for red-black trees algo, it has O(nlogm) but its realy hard as for me. This problem can be solved fast, if you'll try not to consider common solution, but only this ( there is some useful limits in statement, also order is very convenient ) case. Small hint, that I promised: Imagine a big-length wall, like in old platformers, where segments are vertical levels and segment's coords are horizontal coords. Example: 4 2 10 2 3 5 7 6 7 00000011000 00110111000 00111111111 1 are bricks in our wall. Edited by author 14.03.2014 11:03 Re: i'm sad Dmytro Dziuma (DixonD) [Lviv NU] 24 Apr 2014 04:06 Since the input is sorted already, there is a O(n+m) solution |
WA2 | Vetriti | 1987. Nested Segments | 30 Jan 2014 04:08 | 1 |
WA2 Vetriti 30 Jan 2014 04:08 |
To admins: checker is incorrect | Olympic Bear (Nikolay Dubchuk) | 1987. Nested Segments | 6 Nov 2013 00:22 | 2 |
Hi, your checker doesn't check that exactly M lines are printed. My submission #5318694 has received AC. That's OK. In this problem you may output numbers with any whitespaces between them. If all the numbers are right, your solution will be accepted. |
Inclusive or exclusive? | Bruce Merry | 1987. Nested Segments | 19 Oct 2013 13:28 | 2 |
Do the segments include their endpoints? |