|
|
back to boardWA#6 Posted by Anton 24 Feb 2012 06:57 I wonder, what this test case is ... Re: WA#6 Posted by Anton 28 Feb 2012 04:40 I use SQRT-decompossion and I do not care if the same value already exists: add new value to current sqrt(n) segment, recalc gcd on it and then recalc total gcd among all sqrt(n) segments. When I remove an element from some segment, I recalc gcd on this segment and then recalc total. Please, correct me, if my approach isn't OK. How do you find already existing value ? The way I see is to maintenance every segment in ascending order and then quickly search the target value with binary search and replace is with zero. But what is the best way to keep segment in ascending order after new element has been added ? Hope for feedback ^) Edited by author 28.02.2012 04:41 Edited by author 28.02.2012 04:41 Re: WA#6 Posted by vlyubin 11 Apr 2012 08:26 Definitely not STL's map. I tried the same approach as you did except for each of sqrt(n) parts I was keeping a map: number-vector of indices. That gives TL 17 :( I ended up using the segment tree, this might be very helpful: http://codeforces.com/blog/entry/3327 However, I'm still curious about the efficient way for that storage so I created another topic devoted to this :) Edited by author 11.04.2012 08:26 |
|
|