Hello everyone, I tried recently this problem, but unfortunately I got TLE. I am using an *O*(*nlogn*) algorithm as supposed( a segment tree for updating the list and a map to keep track of frequency of each number and it's position ). I think there is some overhead with the update function -- can I rewrite it iteratively ? Any suggestion is welcomed.

Here is my code: link

Note: if someone can redirect me to a non recursive implementation of segment trees that will be great.

I solved it with the same (recursive) approach, but I did not use a map. I compressed the input values by using an auxiliary array (and by sorting it). It passes in 0.171 seconds and 3965 KB.

Can you please explain more. A tiny example will be perfect :)

For the sample input:

I keep a copy of the input, I sort the "copy" thus getting this:

I assign increasing numbers

kto "mark" distinct values (in this case there are 2 distinct values):(while computing this, I store for each

ithe correspondingk).Then, for each

i(from 0 toq- 1), I add/remove the number (which I get from the "original" input) in/from thek-th position.Code here

Thanks dude! Good explanation and good solution too ;)

I've used the segment tree realization, which I know as "Implicit segment tree". The main idea is to build segment tree on whole range of numbers (from 1 to 1000000000 in this problem), but nodes we create only when they are need.

My solution passes in 0.187s with VC++ compiler and 0.343s with G++.

The link that you gave me doesn't work ( empty page ). I am the only one ?

You know what I got it accepted with VC++ compiler too. But, I am highly interested in your solution, please fix the problem.

My solution using an

implicit segment tree. There are at most`100000`

numbers to store; a root-to-leaf path requires`lg(1000000000) ~ 31`

nodes in the segment tree. Pre-allocate a pool of nodes of size`100000 * 31`

, whenever you want to create a new node, fetch it from the pool (faster than malloc-ing at runtime). Update is similar to ordinary segment tree (I use left/right pointers).I've suffered a few days to pass this problem. Even with the right ideia, TLE was the veredict. Then I substitued an iterative approach for the recursive one. Anyway, my iterative update(remove, insert) function is here. Thanks to wil93 for the great solution.

I used the indexing notation of Segment tree (v is the parent of 2*v and 2*v+1) and iterated through the dependent nodes during update; In my solution, On a node I stored gcd due to elements in its left-subtree and gcd due to the elements in its right-subtree. [http://ideone.com/uMRGOV] The space can be reduced also. [http://ideone.com/wqH4Tz]

On a side note, I guess, any balanced Tree representation would work. (Fenwick Trees/ Segment Trees/ Online Treaps etc.,). Hope it helps :)

I am getting WA on the Test-Case #4 .

I have stored all the factors of the number with its occurance in an UNORDERED MAP. I have used set to store the minimum element as HCF will be its factor.

Here is my code .... It would be a great help if someone could tell me whats wrong.