Решение задачи питон

Question

Однажды, после неудачно написанного контеста на 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 тесте, кто может помочь с оптимизацией, либо другим оптимальным решением на любом языке)

Юлия Скрипниченко · Answer

Для решения задачи на Python, где у вас есть операции на сетке размером $n \times m$, следует использовать эффективный подход, так как прямое моделирование сетки может быть неосуществимо из-за её огромного размера. Вот как можно решить задачу с использованием множества для отслеживания уникальных координат, в которых мусор был убран: 
 
### Решение 
 
1. **Используем множества для хранения координат.** Для каждой операции, которая очищает мусор, вычисляем координаты ячеек, которые очищаются, и добавляем их в множество. Поскольку множества не допускают дубликатов, это также гарантирует, что мы не будем подсчитывать одну и ту же ячейку несколько раз. 
 
2. **Учитываем ограничения и особенности**:  
   - При обработке операций вида `+ s` (где `i + j = s`), мы перебираем возможные значения `i` и `j`, которые соответствуют данной операции и не выходят за границы матрицы. 
   - При обработке операций вида `- d` (где `i - j = d`), аналогично перебираем возможные значения `i` и `j`. 
 
### Реализация на Python 
 
```python 
def count_clean_cells(n, m, k, operations): 
    cleaned_cells = set() 
 
    for operation in operations: 
        if operation[0] == '+': 
            s = int(operation[1]) 
            # Проходим по возможным значениям i, j 
            for i in range(1, min(n + 1, s)): 
                j = s - i 
                if 1 <= j <= m: 
                    cleaned_cells.add((i, j)) 
         
        elif operation[0] == '-': 
            d = int(operation[1]) 
            # Проходим по возможным значениям i, j 
            for i in range(1, n + 1): 
                j = i - d 
                if 1 <= j <= m: 
                    cleaned_cells.add((i, j)) 
     
    return len(cleaned_cells) 
 
# Пример использования 
n, m = 4, 4 
k = 4 
operations = [ 
    ('+', '4'), 
    ('+', '2'), 
    ('-', '0'), 
    ('-', '-3') 
] 
 
print(count_clean_cells(n, m, k, operations)) 
``` 
 
### Объяснение 
 
1. **Перебор для операций `+ s`**: 
   - Перебираем все возможные `i` от 1 до `s-1` и вычисляем `j` как `s - i`. 
   - Проверяем, чтобы `j` находился в пределах от 1 до `m`, чтобы не выйти за границы столбцов. 
 
2. **Перебор для операций `- d`**: 
   - Перебираем все возможные `i` от 1 до `n` и вычисляем `j` как `i - d`. 
   - Проверяем, чтобы `j` находился в пределах от 1 до `m`, чтобы не выйти за границы столбцов. 
 
Этот подход использует множества для хранения уникальных очищенных ячеек и позволяет эффективно подсчитать количество уникальных ячеек, в которых был убран мусор.

Егор Шуруповертов · Answer

Я думал ты про змею будешь гворить