Схема мест огромного стадиона почти пуста, поэтому хранить каждую ячейку - напрасная трата памяти. 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
Примеры
Ввод:
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.
Ввод:
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. Следуйте условию и ограничениям выше.