Незваные гости

Автор задачи: Даниил Голов, разработчик: Константин Бац

Заметим, что Землю посетило существ не меньше, чем существ было на Земле одновременно. Очевидно, что это верно не только для существ в целом, но и для существ в каждой из групп.

Покажем, что такую оценку можно достичь, то есть занумеровать прилетающие и улетающие существа, чтобы различных номеров существ в каждой группе было не больше, чем их было одновременно на Земле. Действительно, рассмотрим момент, когда их было больше всего на Земле, и присвоим каждому уникальный номер. Заметим, что это не нарушает условия на логи того, как они будут улетать с Земли и прилетать на нее. Поскольку существа могут прилетать повторно, то больше номеров, чем мы изначально дали, не понадобится.

Таким образом, если считать, что операция + увеличивает некоторый счетчик на один, - уменьшает его, то задача сводится к нахождению максимальных значений у $$$n$$$ различных счетчиков. Для решения такой задачи достаточно хранить массив из $$$n$$$ чисел и явным образом поддерживать число существ на планете в данный момент.

Время работы такого решения — $$$\mathcal{O}(n + m)$$$.