@Artem Ka

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

В качестве собеседования Михаилу предложили очистить от мусора довольно большой двор. Для удобства представим двор как прямоугольную таблицу, состоящую из n строк и m столбцов. Строки пронумерованы сверху вниз числами от 1 до n, а столбцы — слева направо числами от 1 до m. На пересечении i-й строки и j-го столбца находится клетка с координатами (i,j).Изначально в каждой клетке двора лежит огромная куча мусора. Михаил в рамках своего собеседования произвел k
операций, каждая из которых была одного из двух типов:

Убрать весь мусор во всех клетках
(i,j), таких что i+j=s;
Убрать весь мусор во всех клетках (i,j), таких что i−j=d.
Ваша задача — определить количество клеток, в которых Михаил убрал весь мусор.
Формат входных данных
Первая строка содержит два целых числа n и m (1≤n,m≤10**9) — размеры двора. Вторая строка содержит одно целое число k(0≤k≤300000) — количество операций, совершенных Михаилом.

Каждая из следующих k строк содержит описание очередной операции, совершенной Михаилом в следующем формате:
+ s (2≤s≤n+m) — данная операция означает, что Михаил убрал весь мусор во всех клетках (i,j), таких что i+j=s;
- d(1−m≤d≤n−1)— данная операция означает, что Михаил убрал весь мусор во всех клетках (i,j), таких что i−j=d.

Формат выходных данных
Выведите одно целое число — количество клеток, в которых Михаил убрал весь мусор.

Примеры
Входные данные
4 4
4
+ 4
+ 2
- 0
- -3
Выходные данные
7
Примечания
Рассмотрим действия Михаила в примере из условия:

Михаил убирает мусор из клеток (i,j), для которых i+j=4. Это клетки с координатами (1,3), (2,2) и (3,1).
Михаил убирает мусор из клеток (i,j), для которых i+j=2. Это клетка с координатами (1,1).
Михаил убирает мусор из клеток (i,j), для которых i−j=0. Это клетки с координатами (1,1), (2,2), (3,3) и (4,4).
Михаил убирает мусор из клеток (i,j), для которых i−j=−3. Это клетка с координатами (1,4).
Таким образом, мусор был убран из клеток (1,1), (1,3), (1,4), (2,2), (3,1), (3,3) и (4,4).

Написал код на с++, но он падает по времени на 17 тесте, кто может помочь с оптимизацией)

0

@zss

можно заменить на
Аналогично 2-е условие

0

@Artem Ka

Спасибо, но тут уже идея плохая. Я написал по другому. И упало на 47 тесте. Ваше оптимизация вообще выдает неверный ответ).
Буду благодарен вашим идеям по решению =).

0

@KSergey9

Могут ли s и d повторяться в очереди операций?

0

@zss

Идея хорошая,
она существенно сокращает количество итераций.
Проверьте только, правильно ли я написал граничные условия (+-1, <,<=).

0

@KSergey9

Мне думается, что можно обойтись без двумерного массива пересечений.
Надо разложить операции на два set:
операции "+" в set+ (только значения s)
операции "-" в set- (только значения d)

Далее идём по set+ и просто суммируем количество ячеек, которые закрывают эти операции.
У меня вышли такие формулы, но не уверен (E - общая сумма закрытых ячеек):

Для каждого s:
E += min(n, m, s-1), если s <= max(n, m) + 1
E += max(n, m) - s + min(n, m) + 1, иначе

Миниатюры

 

0

@KSergey9

Операции d - они идут "поперёк" операций s, это, конечно, подгадили знатно. Поменять бы i и j местами в разнице -вообще бы шоколад получился.

Ну ладно, раз так - то идём по set-
С одной стороны, для d можно и нужно вывести аналогичные формулы "сколько ячеек какая d добавит".
Но дополнительно нужно вывести формулу "соответствия d и s (через n и m)", и для каждой d искать в set+ есть ли там "соответствующий s". Если есть - то добавлять не просто E+= по формулам d, а вычитать по единице для каждого найденного "соответствия" d и s.

В итоге у нас будет только 1 цикл (ну или два, тут как посмотреть) и только по количеству операций k, а циклов по n и m вовсе не будет.

Но формулы для учета операций из set- мне уже выводить лень.

0

@Artem Ka

да, конечно могут

Добавлено через 2 минуты
Ну, это решение в лоб. А они как правило неэффективны. Я поигрался с границами. Но не смог решить проблему неверного ответа

Добавлено через 6 минут
то есть первые формулы неверны?

0

@KSergey9

Это сейчас кому про что вопрос?

0

@zss

вот тут я ошибся:
условие j-val<=m
т.е j<=m+val

0

@Artem Ka

все равно неверный выдает. 12. но я потыкал, стало выводить 6 и 8, но никак не 7. Добавлено через 51 секунду
на ваш первый ответ. Я так понял алгоритм обломался где формулы?

0

@zss

Еще надо проверить границы 1<=j<=n, получается

0

@Artem Ka

код все равно падает на 17 тесте.

0

@Whabablca

Artem Ka, Решил задачу на Python, могу скинуть код

1

@aqsdds

Whabablca, Быстрым решением?

0

@Artem Ka

Ну спасибо) Давайте посмотрим.

0

@Whabablca

aqsdds, Да

0

@aqsdds

Whabablca, какая у тебя идея?

0

@Artem Ka

ты мой собрат по несчастью?

0

@aqsdds

Artem Ka, Есть такое

0