Разбор добавил Иван Лахтанов

Для решения задачи просто переберем все пары (x, y) прямоугольников и для каждой пары найдем прямоугольник максимальной площади, "начинающийся" в первом из этих двух прямоугольников и "оканчивающийся" во втором. Очевидно площадь такого прямоугольника будет равна сумме ширин всех прямоугольников между x и y, помноженной на минимальную высоту прямоугольников с x по y. Для того чтобы узнавать такие минимумы и суммы за O(1) каждый, будем поддерживать две структуры данных:
для суммы - простейшее RSQ на массиве, для минимумов - sparse table.
Время работы:
1) перебрать все пары прямоугольников - O(N ^ 2)
2) построение RSQ-структуры - O(N)
3) построение sparse table - O(NlogN)
Итого: O(N ^ 2).
При данных ограничениях(учитывая простоту всех операций) данное решение проходит все тесты.