보통 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에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.