Все задачи
Средне Решено: 0 Процент решений: 0%

Разреженная сетка

Храните почти пустую сетку как список ненулевых ячеек и обрабатывайте операции чтения, подсчёта, суммы по строке и удаления столбца.

Чему вы научитесь

  • Хранить только ненулевые ячейки
  • Обновлять сохранённые ключи при сдвиге столбцов
  • Отвечать на запросы, не строя полную сетку

Условие

Схема мест огромного стадиона почти пуста, поэтому хранить каждую ячейку - напрасная трата памяти. SparseGrid хранит только ячейки с ненулевым значением; все остальные ячейки равны 0. Вначале у сетки rows строк, cols столбцов и ни одной сохранённой ячейки. Обработайте по порядку следующие операции:

  • set r c v: ячейка (r, c) получает значение v. Запись 0 удаляет ячейку из хранилища.
  • get r c: вывести значение ячейки (r, c).
  • count: вывести количество ненулевых ячеек.
  • row_sum r: вывести сумму значений в строке r.
  • width: вывести текущее количество столбцов.
  • remove_col c: удалить столбец c. Его ячейки исчезают, все ячейки справа от него сдвигаются на один столбец влево, и столбцов в сетке становится на один меньше.

Строки и столбцы нумеруются с 0, и в момент операции каждый индекс находится внутри сетки.

Реализуйте sparse_grid(rows, cols, operations).

Входные данные

rows: количество строк.

cols: начальное количество столбцов.

operations: операции, которые обрабатываются по порядку.

Выходные данные

Верните результаты операций get, count, row_sum и width в том порядке, в котором они выполнялись.

Ограничения

1 ≤ rows ≤ 1 000 000

1 ≤ cols ≤ 1 000 000

0 ≤ количество операций ≤ 1000

−1 000 000 ≤ v ≤ 1 000 000

Примеры

Пример 1
Ввод:
rows = 3
cols = 4
operations = ["set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"]

Ожидаемый вывод:
expected = [7, 3, 0]
Ввод:
long long rows = 3;
long long cols = 4;
std::vector<std::string> operations = {"set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"};

Ожидаемый вывод:
std::vector<long long> expected = {7, 3, 0};
Ввод:
long rows = 3;
long cols = 4;
string[] operations = new string[] {"set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"};

Ожидаемый вывод:
long[] expected = new long[] {7, 3, 0};

Пояснение

В строке 0 лежат 5 и 2, поэтому её сумма равна 7; сохранено три ячейки; в (1, 1) ничего не записывали, поэтому там 0.

Пример 2
Ввод:
rows = 2
cols = 3
operations = ["set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"]

Ожидаемый вывод:
expected = [9, 2, 1]
Ввод:
long long rows = 2;
long long cols = 3;
std::vector<std::string> operations = {"set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"};

Ожидаемый вывод:
std::vector<long long> expected = {9, 2, 1};
Ввод:
long rows = 2;
long cols = 3;
string[] operations = new string[] {"set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"};

Ожидаемый вывод:
long[] expected = new long[] {9, 2, 1};

Пояснение

Удаление столбца 0 убирает 4 и сдвигает 9 из столбца 2 в столбец 1, поэтому get 1 1 даёт 9, ширина равна 2 и остаётся одна ячейка.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Хорошо подходит словарь из (строка, столбец) в значение; отсутствующий ключ означает 0.

Подсказка 2

Запись 0 в ячейку должна удалять её, чтобы `count` оставался верным.

Подсказка 3

При удалении столбца перестройте словарь: уберите этот столбец, а номера столбцов правее уменьшите на один.

Ожидаемая сложность

время O(q × s), доп. память O(s), s - число сохранённых ячеек

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

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