The problem that I'm doing: 1548B - Integers Have Friends
My submission: 167895313
Basically what I'm doing is finding the maximum length of the subarray in the "diff" array, where their GCD is greater than or equal to 2. I made a GCD segment tree and consider for every index i, I will binary search the greatest j where gcd(diff[i..j]) >= 2. The time complexity of this algorithm should be O(n log^2 n), but I got TLE (5 times with the same code). Is there anything that I'm missing? Thanks in advance.
The actually time complexity for gcd(a, b) is O(log(min(a, b)), so the time complexity of your solution should be O(n log n log 1e18)
Time complexity of your solution is $$$\mathcal{O}(n \log^2 n \log MAX)$$$ because of gcd. It gets accepted with C++ 20 and pragmas though.
It can be proven that the complexity is
O(n log n * (log n + log MAX))Replacing segment tree with RMQ gets AC pretty comfortably. Here's my solution 167921793
(edited)