Problema
O mapa de assentos de um estádio enorme fica quase todo vazio, então guardar cada célula desperdiça memória. Uma SparseGrid guarda apenas as células com valor diferente de zero; todas as outras valem 0. A grade começa com rows linhas, cols colunas e nenhuma célula guardada. Processe estas operações em ordem:
set r c v: a célula (r, c) passa a valerv. Atribuir 0 remove a célula do armazenamento.get r c: informa o valor da célula (r, c).count: informa quantas células são diferentes de zero.row_sum r: informa a soma dos valores da linhar.width: informa o número atual de colunas.remove_col c: apaga a colunac. As células dela desaparecem, todas as células à direita dela andam uma coluna para a esquerda, e a grade fica com uma coluna a menos.
Linhas e colunas são numeradas a partir de 0, e todo índice está dentro da grade no momento da operação.
Implemente sparse_grid(rows, cols, operations).
Entrada
rows: o número de linhas.
cols: o número inicial de colunas.
operations: as operações, processadas em ordem.
Saída
Retorne as respostas de get, count, row_sum e width na ordem em que acontecem.
Restrições
1 ≤ rows ≤ 1 000 000
1 ≤ cols ≤ 1 000 000
0 ≤ número de operações ≤ 1000
−1 000 000 ≤ v ≤ 1 000 000
Exemplos
Entrada:
rows = 3
cols = 4
operations = ["set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"]
Saída esperada:
expected = [7, 3, 0]
Entrada:
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"};
Saída esperada:
std::vector<long long> expected = {7, 3, 0};
Entrada:
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"};
Saída esperada:
long[] expected = new long[] {7, 3, 0};
Explicação
A linha 0 tem 5 e 2, então a soma é 7; há três células guardadas; (1, 1) nunca recebeu valor, então vale 0.
Entrada:
rows = 2
cols = 3
operations = ["set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"]
Saída esperada:
expected = [9, 2, 1]
Entrada:
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"};
Saída esperada:
std::vector<long long> expected = {9, 2, 1};
Entrada:
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"};
Saída esperada:
long[] expected = new long[] {9, 2, 1};
Explicação
Remover a coluna 0 apaga o 4 e desloca o 9 da coluna 2 para a coluna 1, então get 1 1 dá 9, a largura é 2 e sobra uma célula.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Um mapa de (linha, coluna) para valor funciona bem; uma chave ausente significa 0.
Dica 2
Atribuir 0 a uma célula deve apagá-la, para que `count` continue correto.
Dica 3
Quando uma coluna for removida, reconstrua o mapa: descarte essa coluna e diminua em um os números das colunas maiores.
Complexidade esperada
tempo O(q × s), espaço extra O(s), s = células guardadas
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.