Here is a O(N log N) solution. Observe that the program's output can be verified by some algorithm which answers the question "Does any rectangle have median ≤ X?" This query can be answered in O(n2) time. A rectangle has median ≤ X if and only if it contains more values ≤ X than otherwise. Assign all cells in the grid a 'value' according to a 'threshold' function: -1 if greater than X, 0 if equal to X, 1 if less than X. Using the well-known cumulative data structure for queries on rectangular sums, try all possible rectangle locations and return "yes" if the 'values' inside any sum to ≥ 0. We simply binary search values of X to find the minimum value for which the answer is "yes".
N.B. An O(N log N) algorithm suffices for 100% score.O(N logN) 방법이 있긴하다는데 잘 이해가 안가네요 ㅠㅠ