1749. Destroy the cube

时间限制 4000 ms   内存限制 512 MB

There is a chessboard with $n$ rows and $n$ columns, every position is black or white. It is defined that $c(x,y)$ means the color of the position in the $x$th row and the $y$th column, and it is guaranteed that $c(x,y)=c(y,x)=c(x,n-y+1)=c(n-x+1,y)$ for any $1\leq x,y\leq n$, which shows it is quite symmetry. Also because of this, only the colors of the positions $(x,y)$ which satisfies $x\leq y\leq\lfloor\frac{n+1}{2}\rfloor$ are given, and the number of the given black position is $t$ in total. Now HazelFan has a big cube with $n$ layers and $n$ rows and $n$ lines, and its six sides are all same as the chessboard. For the three pairs of opposite sides, for each black position on one side, he will dig through the cube from the position straight to a black position on the other side. Please tell him after he destroys the cube, how many little cubes are left.

输入数据

The first line contains a positive integer $T(1\leq T\leq5)$, denoting the number of test cases.
For each test case:
The first line contains two positive integers $n,t(1\leq n\leq6\times10^4,1\leq t\leq1.2\times10^5)$.
The next $t$ lines, each line contains two positive integers $x,y(1\leq x\leq y\leq\lfloor\frac{n+1}{2}\rfloor)$, denoting a given black position.

输出数据

For each test case:
A single line contains a nonnegative integer, denoting the answer.

样例输入

复制
2
3 1
2 2
5 2
2 3
3 3 \n
 · \n
 · \n
 · \n
 · \n
 · \n

样例输出

复制
20
76  \n
  \n

提交

请先 登录

Source

2017 Multi-University Training Contest - Team 7

© 2024 FAQs Contact About