시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1.5 초 | 512 MB | 93 | 49 | 42 | 51.852% |
You are given a matrix of size 2n × 2n, initially painted in white color. The color of a cell can be either black or white. Let’s define the price of a matrix as:
You are given q queries. Each query gives you the number of row/column x, and you have to change the color of all cells in this row/column (i.e., if a cell is white, it will be black; if a cell is black, it will be white) and find the price of the new matrix.
The first line contains two integers n and q (0 ≤ n ≤ 20, 1 ≤ q ≤ 106) where n means that the size of the matrix is 2n × 2n and q means that there are going to be q queries.
Each of the next q lines contains two integers t and x (0 ≤ t ≤ 1, 1 ≤ x ≤ 2n). If t = 0, then the x-th row will be changed; otherwise, the x-th column.
For each query, print a matrix price.
2 7 1 3 0 2 1 1 1 4 0 4 0 3 1 1
13 17 21 17 21 17 13
In the sample, after each query the matrix will be as follows:
ICPC > Regionals > Europe > Southeastern European Regional Contest > SEERC 2018 G번