| ENG RUS | Timus Online Judge |
Discussion of Problem 2062. Ambitious ExperimentandreyDagger If you're using segment tree and getting TLE // Problem 2062. Ambitious Experiment 28 Oct 2021 17:41 Use Fenwick tree instead of segment tree hadooken [Hint] If you got TLE with segment tree [1] // Problem 2062. Ambitious Experiment 5 Dec 2019 23:47 LaVuna [NULP] Re: [Hint] If you got TLE with segment tree // Problem 2062. Ambitious Experiment 28 Nov 2020 02:08 It worked. Optimization is really out of this world) Михаил TLE18? // Problem 2062. Ambitious Experiment 23 Jul 2020 19:51 Mahilewets How to achieve such an incredible speed like MrWindows' 0.4 sec? [1] // Problem 2062. Ambitious Experiment 6 Aug 2017 12:24 I have thought about something like lazy calculations model Mahilewets Re: How to achieve such an incredible speed like MrWindows' 0.4 sec? // Problem 2062. Ambitious Experiment 6 Aug 2017 18:10 Sorry, MrDindows. baske WA Test #9 [2] // Problem 2062. Ambitious Experiment 21 Jul 2016 10:17 Can any one help me? I got WA in test #9. But I have no idea where I made a mistake. I need some tests. I might ignored something important. Thanks. Xudong_LI Re: WA Test #9 [1] // Problem 2062. Ambitious Experiment 2 Aug 2016 16:33 me too,got WA in test #9. Have you solve it? quick(YaroslavlSU) Re: WA Test #9 // Problem 2062. Ambitious Experiment 13 Aug 2016 03:36 long long Xudong_LI I got Time limit exceeded on test #10 // Problem 2062. Ambitious Experiment 2 Aug 2016 16:47 Adhambek use SQRT decompose. [3] // Problem 2062. Ambitious Experiment 27 Oct 2015 13:53 Sunnat Re: use SQRT decompose. [2] // Problem 2062. Ambitious Experiment 27 Oct 2015 18:42 You may use segment_tree instead of sqrt_decompose, my solution is segment_tree with very easy idea. Edited by author 27.10.2015 18:43 lyonlys Re: use SQRT decompose. [1] // Problem 2062. Ambitious Experiment 28 Oct 2015 01:07 So, what is the detail of the "segment tree" solution? How to update and query? Thx, in advance.:) Alexandru Valeanu Re: use SQRT decompose. // Problem 2062. Ambitious Experiment 15 Nov 2015 06:01 A fenwick tree will be faster. Hint : you just need range updates and point queries. My complexity : O(Q * logN * 180). lyonlys I would like to know how to solve this problem faster, as I pass it with 2.8s. // Problem 2062. Ambitious Experiment 25 Oct 2015 00:20 My solution: Cutting the array into blocks, so I can now update a segment with O(sqrt n) each query; therefore, I can get the increase in O(1) while scanning each factor (at most 180 in total). It is obvious that I should prepare all the factors for each number. The complexity of the algorithm is O((sqrt(n) + 180) * m + 180 * n). and .. I reduce a lot of modular and divide operations to get this AC. :P Edited by author 25.10.2015 00:21
|