Средне Решено: 0 Процент решений: 0%

Sparse Grid

Keep a mostly empty grid as a list of its non-zero cells and answer get, count, row sum and column removal operations.

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

  • Store only non-zero cells
  • Update stored keys when columns shift
  • Answer queries without building the full grid

Условие

Показать перевод

A seating chart for a huge stadium is mostly empty, so storing every cell wastes memory. A SparseGrid stores only the cells that hold a non-zero value; every other cell is 0. The grid starts with rows rows, cols columns and no stored cells. Process these operations in order:

  • set r c v: cell (r, c) becomes v. Setting 0 removes the cell from storage.
  • get r c: output the value of cell (r, c).
  • count: output how many cells are non-zero.
  • row_sum r: output the sum of the values in row r.
  • width: output the current number of columns.
  • remove_col c: delete column c. Its cells disappear, every cell to its right moves one column left, and the grid has one column fewer.

Rows and columns are numbered from 0, and every index is inside the grid at the time of the operation.

Implement sparse_grid(rows, cols, operations).

Input

rows: The number of rows.

cols: The starting number of columns.

operations: The operations, processed in order.

Output

Return the outputs of get, count, row_sum and width in the order they happen.

Ограничения

1 ≤ rows ≤ 1,000,000

1 ≤ cols ≤ 1,000,000

0 ≤ number of operations ≤ 1,000

−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};

Пояснение

Row 0 holds 5 and 2, so its sum is 7; three cells are stored; (1, 1) was never set, so it is 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};

Пояснение

Removing column 0 deletes the 4 and slides the 9 from column 2 to column 1, so get 1 1 is 9, the width is 2 and one cell is left.

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

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

Подсказка 1

A map from (row, column) to value works well; a missing key means 0.

Подсказка 2

Setting a cell to 0 should delete it so `count` stays right.

Подсказка 3

When a column is removed, rebuild the map: drop that column and shift larger column numbers down by one.

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

O(q × s) time, O(s) extra space, s = stored cells

Ссылки

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

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

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

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

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

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