I know the O(n^2) solution to the problem. It tries to make a rectangle for every pair of points. This approach times out for subtask 2 which needs an O(n) or O(n.logn) solution.
So what is the O(n) approach for this problem?
In case you are interested, my O(n^2) solution is here : Ideone
I think that a sliding window like approach could work here. Hints are also appreciated.
@shreerockz15 you can do this in O(lb). You make an array of size 10^5 and then at which ever place the point is given you mark a[x] = y otherwise you mark a[x] = 500. You then check for all heights what is the maximum continuos points such that its a[x] is <= height. ans = max(height(width+1)) for all heights 1 to 500 and its respective max continuos a[x] <= h.
Here’s my solution - https://www.codechef.com/viewsolution/12290874