|
|
O(n*sqrt(n)*log(n)) enough?
Upd: OK with this complexity. But 2.7 c++. How to solve with 0.1 second?
Edited by author 21.02.2026 00:26 Persistent segment tree is NOT NEEDED! Why for Q: 1 6 the answer is 5 6 and not 2 6 ?
Having input "17 11 -1 -4 20 -24"
for 5 6 we have 20 -24 = -4
and for 2 6 we have 11 -1 -4 +20 -24 = 2
why -4 is better than 2? Because we need to find 2 separate indexes i < j : |a[i] + a[j]| is minimal.
Not sum of segment |a[i]+a[i+1]+...+a[j]|, but only 2 numbers a[i] and a[j]. |
|
|
