I implemented O(N.N^1/3 + M) solution for this problem here http://www.codechef.com/viewsolution/6678169 and even tried to reduce constants, but still it didn’t pass. Was any faster solution possible or it is because I used JAVA?
1 Like
You can solve it in O(NlogN+M) using sparse table.
This problem have no idea behind it, you only have to write solution carefully; lot of solutions with right asymptotic got TL. For example, I had to change A[n][m] to A[m][n] to avoid large jumps over memory, and it was enough to make my solution pass 
1 Like