中級 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 つずつ開いてみましょう。

ヒント 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用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。