| MemSQL start[c]up Round 1 |
|---|
| Закончено |
Красная Шапочка и Иван Дурак внезапно обнаружили себя за тридевять земель, в мире, который представлен огромным цилиндром. На одном из оснований цилиндра (назовем его «верх цилиндра») вся поверхность занята некоторым царством, на другом основании (назовем его «низ цилиндра») вся поверхность занята некоторым государством, а боковая поверхность цилиндра целиком покрыта морем.
В один прекрасный день царь некоторого царства и государь некоторого государства решили, что не дело это морю пропадать зря, когда его можно превратить в землю и тем самым расширить границы своих владений. Для того, чтобы писари могли вести учет происходящего, море представили в виде сетки, состоящей из r строк и c столбцов — каждая ячейка этой сетки представляет некоторую прямоугольную область на стороне цилиндра. Строки занумерованы от 1 до r сверху вниз, а столбцы — от 1 до c слева направо. Две ячейки считаются смежными, если у них есть общая сторона. Кроме того, если две ячейки расположены в одной строке — одна в самом левом столбце, а другая — в самом правом, то они тоже смежны.
Изначально все ячейки покрыты морем. Теперь царь и государь планируют превратить часть из них в землю одна за одной согласно некоторому порядку, который Вам предоставлен.
Единственной проблемой на пути выполнения их плана является то, что по морю пролегает важный торговый маршрут. Поэтому в процессе превращения моря в землю Вы хотите, чтобы в каждый момент времени существовала последовательность ячеек, удовлетворяющих следующим свойствам (такую последовательность ячеек назовем торговым маршрутом):
- Все ячейки в последовательности являются морем (еще не превращены в землю).
- Первая ячейка в последовательности находится в первой строке (самой верхней).
- Последняя ячейка в последовательности находится в последней строке (самой нижней).
- Любые две последовательные ячейки в последовательности смежны друг с другом.
Красной Шапочке и Ивану Дураку поручили переработать план так, чтобы в любой момент времени существовал хотя бы один торговый маршрут. План Ивана и Панамки очень прост — каждый раз, когда ячейка должна быть превращена из моря в землю, они проверяют, не получится ли так, что после превращения не останется ни одного торгового маршрута. Если хотя бы один маршрут остается, они превращают море в землю на этой ячейке, и переходят к следующей ячейке. Если ни одного маршрута не остается, они не превращают эту ячейку в землю, и переходят к следующей ячейке.
Ваша задача симулировать этот процесс, и определить, сколько же ячеек в конечном итоге будет превращено из моря в землю.
В первой строке содержатся три целых числа r, c и n (1 ≤ r, c ≤ 3000, 1 ≤ n ≤ 3·105). В последующих n строках перечислены ячейки в том порядке, в котором царь и государь хотят превратить их в землю. Каждая такая строка содержит два целых числа: ri и ci (1 ≤ ri ≤ r, 1 ≤ ci ≤ c) — соответственно номер строки и номер столбца ячейки, которую надо превратить в землю. Все ячейки в плане попарно различны.
В единственной строке выведите целое число — сколько ячеек из плана Красная Шапочка и Иван Дурак смогут перекрасить, следуя их плану.
3 4 9
2 2
3 2
2 3
3 4
3 1
1 3
2 1
1 1
1 4
6
Ниже представлены превращения, которые были выполнены (красной линией показан возможный торговый маршрут, желтым цветом или красным цветом помечается текущая рассматриваемая ячейка, в зависимости от того существует торговый маршрут или нет):
После этого превращения не остается ни одного маршрута, поэтому превращение не осуществлено.
Маршрута нет, превращение не осуществлено.
Не забывайте, что самая левая и самая правая ячейки одной строки смежны.
Маршрута нет, превращение не осуществлено.
Соответственно, результат:
В землю превращено шесть ячеек.
