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 i dont have any idea why wa5.. Edited by author 02.07.2022 22:06 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 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! 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 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 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 I've got Runtime error in Test 2. I've written the code in Java. Could anybody share the test case for the Test2? 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 TLE24 with 3 different codes <3 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." Algo O(nm) works for 1.046 sec, but O(2n) uses more than 65536kb. Edited by author 02.01.2014 15:28 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 Since the input is sorted already, there is a O(n+m) solution 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. Do the segments include their endpoints? |
|