First refer to the official editorial.

We first describe an \(O(N \log N \log \max A)\) solution.

First we collect, sort, and deduplicate the set of all possible lengths obtained by repeatedly dividing sticks of length \(A_i\). This is used both for coordinate compression and as candidates for the median \(X\).

Then we use two-pointer technique rather than binary search. As we decrease the candidate median \(X\), we may split more sticks of length \(2X - 1\) or greater. We then have to find the \(\frac{N+M+1}{2}\) shortest sticks that are of length \(X\) or longer. This can be done using segment trees that support point update, range sum, and binary search over range sum (e.g. the max_right function in the AtCoder library).

To get this down to \(O(N \log \max A)\) we must optimize both steps.

The first step of collecting the set can be optimized by bit-trie or radix sort, however you might not see much practical improvement from this optimization, and is thus presented mostly for theoretical interest. You could still see much practical improvement by optimizing the second step.

The second step requires us to do away with the segment trees. It requires the observation that the upper-bound of the window of “\(\frac{N+M+1}{2}\) shortest sticks that are of length \(X\) or longer” does not increase as \(X\) decreases. [This is because before the window bounds are updated, any sticks removed from the window is replaced by at least as many sticks added back to the window.] Thus we can also use two-pointer technique to maintain its sum.

Sample code (Rust). Note that my submission that uses the standard library sort rather than radix sort (link) actually runs faster.