Прямоугольники, Площадь максимального прямоугольника

Question

Прямоугольники

Дана последовательность N прямоугольников различной ширины и высоты (wi,hi). Прямоугольники расположены, начиная с точки (0,0), вправо на оси OX вплотную друг за другом. Требуется найти M — площадь максимального прямоугольника (параллельного осям координат), который можно вырезать из этой фигуры.

Формат входных данных

В первой строке задано число N(1≤N≤105). Далее идут N строк. В каждой строке содержатся два числа: ширина и высота i-го прямоугольника (1<wi≤310^4, 0≤hi≤310^4).

Формат выходных данных Выведите искомое число M. Примеры: Ввод:
3
4 3
2 1
2 5
Вывод:
12
Ввод:
3
4 3
2 1
3 5
Вывод:
15
Написал код, но тестирующая система пишет "Программа выдаёт ошибку в процессе выполнения" Вот, подскажите в чём ошибка:

a = [-int(2e9) - 1]
n = int(input())
for i in range(n):
    w, h = map(int, input().split())
    a.extend([h] * w)
a.append(-int(2e9) - 1)
n = len(a) - 2
r = [0] * (n + 2)
l = [0] * (n + 2)
st = [0]
s = []
for i in range(1, n + 2):
    while a[st[-1]] > a[i]:
        r[st.pop()] = i
    st.append(i)
st = [n + 1]
for i in range(n, 0, -1):
    while a[st[-1]] > a[i]:
        l[st.pop()] = i
    st.append(i)
for i in range(len(a)):
    s.append(a[i] * (abs(r[i] - l[i] - 1)))
print(max(s))

Answer 1

Если честно, я не нашел конкретного теста, на котором программа падает, но хочу кое-что отметить.

В первую очередь при решении олимпиадной задачи по информатике надо внимательно посмотреть на ограничения, после чего решить задачу максимально просто и быстро. В данном случае N <= 105, поэтому линейный алгоритм тут абсолютно ни к чему. Так что вам не стоило использовать очереди минимумов, причем так, что в худшем случае вы создадите массив на 3*10^7 элементов, который никак не обработается за тайм лимит на питоне. Лучше напишите самый очевидный и простой кубический алгоритм:

n = int(input())
a = [[int(i) for i in input().split()] for _ in range(n)]
ans = a[0][0] * a[0][1]
for left in range(n):
    for right in range(left, n):
        min_h = a[left][1]
        sum_w = 0
        for i in range(left, right + 1):
            min_h = min(min_h, a[i][1])
            sum_w += a[i][0]
        area = min_h * sum_w
        ans = max(ans, area)
print(ans)

Если вдруг он не пройдет по времени и религия не позволяет вам писать на C++, то sum_w можно считать префиксными суммами, и это ускорит программу почти в два раза. Если вдруг даже так она упадет с TLE, то только тогда извращайтесь с очередями минимумов на сжатых координатах или пишите дерево отрезков минимумов на питоне (пожалуйста, не надо).

И желаю вам больше не выкладывать код и задачи с отборочных соревнований, пока они не закончатся (если они еще не закончились), потому что это запрещено правилами и является очень неспортивным поведением.

Upd: Как заметил комментатор ниже, вы скорее всего некорректно вставили условие (и скорее всего не прочитаете даже этот ответ), так что мое решение является неверным. Однако ваше собственное решение точно также не укладывается в стандартную секунду, так как при максимальном тесте вы не успеете создать массив на 3*10^7 элементов на питоне.

Решение для ограничений N <= 10^5, Wi <= 3*10^4 - это ваше решение с очередями минимумов, но со сжатием координат.

БЛОГ НА HUSL

Прямоугольники, Площадь максимального прямоугольника

Ответы (1 шт):