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

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

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

Найдем теперь минимально возможное количество различных посетителей. Заметим, что если в какой группе ни одно существо ни разу не посетило Землю, то ответ для такой группы — $$$0$$$. Иначе ответ хотя бы один. При этом последовательность событий в логе можно выстроить в пары событий: «существо прилетело» – «существо улетело». При этом, если событий вида «существо прилетело» больше, чем событий «существо улетело», то различных существ на земле побывало не меньше, чем разность количества событий этих двух видов.

Таким образом, для каждой группы необходимо подсчитать количество событий «существо прилетело», пусть оно равно $$$cnt_+$$$, и количество событий «существо улетело», пусть оно равно $$$cnt_-$$$. Тогда, максимальное количество различных существ, побывавших на Земле, равно $$$cnt_+$$$. Если $$$cnt_+>0$$$, то минимально возможное количество различных посетителей равно $$$\max(cnt_+ - cnt_-, 1)$$$, иначе $$$0$$$.

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