Задача 4. Трапеза для героев Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 512 мегабайт
После очередной победы над пришельцами K героев одного известного фильма собрались вместе
в кафе. Среди героев есть правши и левши. Они хотят сесть за длинным прямоугольным столом с
одной стороны этого стола так им лучше наблюдать за происходящим в кафе. Места за столом
последовательно пронумерованы, всего за столом N мест. Герои могут садиться не рядом друг с
другом. За столом могут остаться свободные (незанятые) места. Если на соседних (расположенных
последовательно друг за другом) местах по правую руку от правши оказывается левша именно в
таком порядке, то им будет неудобно есть. Грут обеспокоен такой ситуаций и хочет узнать много
ли пар героев сидят неудобно.
Форматвходныхданных
В первой строке записано целое число N (1 6N 6106) количество мест за столом.
Во второй строке записано целое число K (1 6K 63 ·105) количество героев.
Далее следуют K строк, к каждой из которых содержится информация о соответствующем герое:
номер места, и 0 если герой - правша, или 1 если герой - левша.
Гарантируется, что номера мест всех героев попарно различны.
Форматвыходныхданных
Выведите одно целое число количество пар героев, которым неудобно сидеть за столом.
Системаоценки
за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи
и необходимых подзадач успешно пройдены.
Ограничения
Подзадача K Дополнительные
ограничения
Необходимые
подзадачи
Информация о
проверке
0 0 Тесты из условия полная
1 20 1 6K 65 000 полная
2 20 1 6K 63 ·105 Количество левшей
не превосходит 100 первая ошибка
3 60 1 6K 63 ·105 1, 2 первая ошибка