Getting TLE while doing binary search on segment tree

Правка en1, от haiender288, 2022-08-11 20:10:00

The problem that I'm doing: 1548B - У чисел есть друзья

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.

Теги segment tree, gcd, binary search

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский haiender288 2022-08-11 20:10:00 566 Initial revision (published)