I wonder, what this test case is ...

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

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