Помощь с оптимизацией задачи с++

Question

Помощь с оптимизацией задачи с++

Артем Как Ученик (124), на голосовании 1 месяц назад

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

 #include  
using namespace std; 
struct cell_hash { 
    size_t operator()(const pair& cell) const { 
        return hash()(cell.first) ^ hash()(cell.second); 
    } 
}; 
  
int main() { 
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    long long n, m, k; 
    cin >> n >> m >> k; 
    unordered_set, cell_hash> vec; 
    for (long long i = 0; i < k; ++i) { 
        char op; 
        long long val; 
        cin >> op >> val; 
        if (op == '+') { 
            for (long long j = 1; j <= n; ++j) { 
                long long i = val - j; 
                if (i >= 1 && i <= m) { 
                    vec.insert({j, i}); 
                } 
            } 
        } else if (op == '-') { 
            for (long long j = 1; j <= n; ++j) { 
                long long i = j - val; 
                if (i >= 1 && i <= m) { 
                    vec.insert({j, i}); 
                } 
            } 
        } 
    } 
    cout << vec.size() << endl; 
    return 0; 
}

Answer 1

Для решения этой задачи оптимальным образом нужно учитывать масштабность проблемы, так как прямое использование матриц с размерами до \(10^9 \times 10^9\) недопустимо. Вместо этого можно использовать наборы (set) для хранения уникальных значений, которые представляют клетки, очищенные мусором.

### Основные шаги для оптимизации решения:

1. **Использование множеств (sets)**:
- Используем множества для хранения уникальных значений строк и столбцов, очищенных разными операциями.
- Для каждой операции типа `+ s`, храните индексы строк и столбцов, которые соответствуют сумме `s`.
- Для операций типа `- d`, храните индексы строк и столбцов, которые соответствуют разности `d`.

2. **Определение количества очищенных ячеек**:
- Посчитайте количество уникальных ячеек, которые затрагиваются всеми операциями.

### Решение на C++

Ниже представлен оптимизированный код на C++:

```cpp
#include <iostream>
#include <set>
#include <unordered_map>

using namespace std;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);

long long n, m, k;
cin >> n >> m >> k;

set<long long> plusOperations;
set<long long> minusOperations;

while (k--) {
char op;
long long val;
cin >> op >> val;

if (op == '+') {
plusOperations.insert(val);
} else if (op == '-') {
minusOperations.insert(val);
}
}

// Calculate the unique positions
unordered_map<long long, int> cellCount;

for (const auto& s : plusOperations) {
if (s < 2 || s > n + m) continue;
for (long long i = max(1LL, s - m); i <= min(n, s - 1); ++i) {
long long j = s - i;
if (j >= 1 && j <= m) {
cellCount[i * m + j] = 1;
}
}
}

for (const auto& d : minusOperations) {
for (long long i = max(1LL, 1 + d); i <= min(n, m + d); ++i) {
long long j = i - d;
if (j >= 1 && j <= m) {
cellCount[i * m + j] = 1;
}
}
}

cout << cellCount.size() << '\n';
return 0;
}
```

### Объяснение:

1. **Считывание входных данных**:
- Считываем размеры двора и количество операций.
- Храним операции в двух множествах: одно для операций типа `+`, другое — для операций типа `-`.

2. **Обработка операций**:
- Для операций типа `+ s` определяем все возможные клетки, которые могут быть очищены при данной сумме `i + j = s`.
- Для операций типа `- d` определяем все клетки по разности `i - j = d`.

3. **Подсчет уникальных клеток**:
- Храним все уникальные позиции в `unordered_map` (можно использовать и `set`), чтобы избежать дублирования.

Этот код эффективно обрабатывает задачи с большими размерами ввода, используя только необходимые данные и минимизируя память.

Answer 2

 #include 
#include 
#include 
 
long long calc(int n, int m, const std::vector& dVector, std::vector& sVector) {
	std::sort(sVector.begin(), sVector.end());
	long long cells = 0;
	for (auto s : sVector)
		cells += s - 1 - std::max(s - 1 - n, 0) - std::max(s - 1 - m, 0);
	for (auto d : dVector) {
		const auto dLength = d >= 0 ? std::min(n - d, m) : std::min(n, m + d);
		d = std::abs(d);
		const auto low = std::upper_bound(sVector.cbegin(), sVector.cend(), d);
		const auto high = std::upper_bound(low, sVector.cend(), d + 2 * dLength);
		cells += dLength - (high - low);
	}
	return cells;
}

int main() {
	int n, m, k;
	std::cin >> n >> m >> k;
	std::vector sOdds, sEvens, dOdds, dEvens;
	for (int i = 0; i < k; ++i) {
		char op;
		int val;
		std::cin >> op >> val;
		if (op == '+')
			(val & 1 ? sOdds : sEvens).emplace_back(val);
		else
			(val & 1 ? dOdds : dEvens).emplace_back(val);
	}
	std::cout << calc(n, m, dOdds, sOdds) + calc(n, m, dEvens, sEvens);
	return 0;
}