Problema
El plano de asientos de un estadio enorme está casi vacío, así que guardar cada celda desperdicia memoria. Una SparseGrid guarda solo las celdas con un valor distinto de cero; todas las demás valen 0. La cuadrícula empieza con rows filas, cols columnas y ninguna celda guardada. Procesa estas operaciones en orden:
set r c v: la celda (r, c) pasa a valerv. Asignar 0 elimina la celda del almacenamiento.get r c: produce el valor de la celda (r, c).count: produce cuántas celdas son distintas de cero.row_sum r: produce la suma de los valores de la filar.width: produce la cantidad actual de columnas.remove_col c: elimina la columnac. Sus celdas desaparecen, todas las celdas a su derecha se mueven una columna a la izquierda y la cuadrícula queda con una columna menos.
Las filas y las columnas se numeran desde 0, y cada índice está dentro de la cuadrícula en el momento de la operación.
Implementa sparse_grid(rows, cols, operations).
Entrada
rows: la cantidad de filas.
cols: la cantidad inicial de columnas.
operations: las operaciones, que se procesan en orden.
Salida
Devuelve las salidas de get, count, row_sum y width en el orden en que ocurren.
Restricciones
1 ≤ rows ≤ 1,000,000
1 ≤ cols ≤ 1,000,000
0 ≤ número de operaciones ≤ 1,000
−1,000,000 ≤ v ≤ 1,000,000
Ejemplos
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"]
Salida 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"};
Salida 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"};
Salida esperada:
long[] expected = new long[] {7, 3, 0};
Explicación
La fila 0 tiene 5 y 2, así que su suma es 7; hay tres celdas guardadas; a (1, 1) nunca se le asignó un valor, así que vale 0.
Entrada:
rows = 2
cols = 3
operations = ["set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"]
Salida 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"};
Salida 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"};
Salida esperada:
long[] expected = new long[] {9, 2, 1};
Explicación
Al eliminar la columna 0 se borra el 4 y el 9 de la columna 2 pasa a la columna 1, así que get 1 1 da 9, el ancho es 2 y queda una celda.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Un mapa de (fila, columna) a valor funciona bien; una clave que no existe significa 0.
Pista 2
Asignar 0 a una celda debe borrarla para que `count` siga siendo correcto.
Pista 3
Cuando se elimina una columna, reconstruye el mapa: quita esa columna y resta uno a los números de columna mayores.
Complejidad esperada
tiempo O(q × s), espacio extra O(s), s = celdas guardadas
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.