Puppy and cats
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Tuzik is a very brave puppy. But there is still one thing he is afraid of - big black cats. He always tries to avoid them.
Tuzik's city can be represented as an N x N grid. Each cell of the city can either contain cats or not. Tuzik knows that K cells of the city are dumps. If a cell is a dump, then each diagonal that contains this cell is full of cats (all cells of this diagonal contain cats). Two cells with corresponding coordinates (i, j) and (x, y) are on one diagonal if either x + y equals i + j or x - y equals i - j.
You are given integers N and coordinates of K dumps. Please find the number of cells which are free of cats.
The first line of the input contains an integer T, denoting the number of test cases. Each test case starts with a line containing space-separated integers N and K. Each of the following K lines contain two space-separated integers xi and yi - coordinates of each dump. All the dumps are pairwise different.
For each test case, output a single line containing one integer - number of cells that are free of cats.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 106
- 0 ≤ K ≤ 105
- 1 ≤ xi, yi ≤ N
- Subtask #1 [22 points]: 1 ≤ N ≤ 500, 0 ≤ K ≤ 104
- Subtask #2 [24 points]: 1 ≤ N ≤ 1000, 0 ≤ K ≤ 105
- Subtask #3 [23 points]: 1 ≤ N ≤ 106, 0 ≤ K ≤ 1
- Subtask #4 [31 points]: no additional constraints
Input: 1 3 2 1 2 3 2 Output: 5
We have cells (2, 1) (2, 3) on the same diagonals with (1, 2) or (3, 2). Thus 4 cells are occupied by cats and 5 are free of cats.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.