Hi,

I'm solving this POI problem: http://main.edu.pl/en/archive/oi/15/kup . Basically, given an integer k(1 ≤ k ≤ 10⁹) and an N by N square grid(1 ≤ N ≤ 2000) of non-negative integers, you have to find some rectangle in the grid such that its sum is between k and 2k, inclusive.

I can come up with O(n³) solution using prefix sums and monotonicity, however to make the problem fit the time limit I need something faster. By google translating the editorial, I think it's divide and conquer, but I couldn't understand the details as the translation was very bad. I would appreciate any help on this problem :D