All Tracks Data Structures Hash Tables Basics of Hash Tables Problem

Cells in a matrix

Algorithms, Basic Math, Basics of Hash Tables, Data Structures, Datastructures, Hash Tables


You are given an integer \(N\) denoting an \(N \times N\) matrix. Initially, each cell of the matrix is empty. You are given \(K\) tasks. In each task, you are given a cell \((i,j)\) where cell \((i,j)\) represents the \(i^{th}\) row and \(j^{th}\) column of the given matrix.

You have to perform each task sequentially in the given order. Each task is described in cell \((i,j)\). For each task, you have to place \(X\) in each cell of row \(i\) and each cell column \(j\). After you complete each task, you are required to print the number of empty cells in the matrix.  

Input format

  • The first line contains two space-separated integers \(N\) and \(K\) where \(N\) is the number of rows and columns in the given matrix and \(K\) is the number of tasks respectively.
  • Next \(K\) lines contain two space-separated integers \(i\) and \(j\).

Output format

Print \(K\) space-separated integers denoting the number of empty cells in the matrix.


\(1 \le N \le 10^5\)

\(1 \le K \le 1000\)

\(1 \le i , j \le N\)


3 3
1 1
1 3
3 2
4 2 0

Initally all the cells [{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}] are empty.

After the first task:
Empty cells are [{2, 2}, {2, 3}, {3, 2}, {3, 3}]. Therefore, the answer is 4.

After the second task:
Empty cells are [{2, 2}, {3, 2}]. Therefore, the answer is 2.

After the third task:
No cells remain empty. Therefore, the answer is 0.

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications