TopCoder

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

Tags

Description

完整題本 PDF:中文英文馬來文

相信大家都很熟悉圈圈叉叉這款經典的紙筆遊戲。不過,在這道題目中,我們將要在一個巨大的網格上玩這個遊戲!




相較於一般的版本,我們將會在一個 $N \times N$ 的網格上進行遊戲。兩位玩家和一般的版本一樣輪流在棋盤上劃記,第一位玩家劃記 $\texttt{X}$,第二位玩家劃記 $\texttt{O}$。另一個與一般遊戲的差異在於玩家可以在已經劃過的格子上劃記,一個已經被劃記過的格子如果再被劃一次,那新的劃記會覆蓋過原本的。每一步後,每位玩家當前的分數會是完全由他們的劃記所組成的水平、垂直和對角線數量。

現在,給你每一步玩家劃記了哪個座標,請你計算每一步後兩位玩家的分數。

Input Format

輸入的第一行有兩個正整數 $N, Q$。

接下來的 $Q$ 行,每行有兩個正整數 $x_i, y_i$。$(x_i, y_i)$表示第 $i$ 步玩家劃記的座標。如果 $i$ 是奇數,則這一步是第一位玩家下的;如果 $i$ 是偶數,則這一步是第二位玩家下的。

  • $2 \leq N \leq 1000$
  • $1 \leq Q \leq 10 ^ 6$
  • $1 \leq x_i, y_i \leq N$

Output Format

輸出 $Q$ 行,每行兩個整數,分別表示在第 $i$ 步後第一位玩家和第二位玩家的分數。

Sample Input 1

3 6
2 2
1 1
1 2
2 1
3 2
3 2

Sample Output 1

0 0
0 0
0 0
0 0
1 0
0 0

Sample Input 2

3 8
1 1
1 3
3 3
3 1
2 2
2 2
2 2
2 2

Sample Output 2

0 0
0 0
0 0
0 0
1 0
0 1
1 0
0 1

Hints

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 2097152 65536
1 1000 2097152 65536
2 1000 2097152 65536
3 1000 2097152 65536
4 1000 2097152 65536
5 1000 2097152 65536
6 1000 2097152 65536
7 1000 2097152 65536
8 1000 2097152 65536
9 1000 2097152 65536
10 1000 2097152 65536
11 1000 2097152 65536
12 1000 2097152 65536
13 1000 2097152 65536
14 1000 2097152 65536
15 1000 2097152 65536
16 1000 2097152 65536
17 1000 2097152 65536
18 1000 2097152 65536
19 1000 2097152 65536
20 1000 2097152 65536
21 1000 2097152 65536
22 1000 2097152 65536
23 1000 2097152 65536
24 1000 2097152 65536
25 1000 2097152 65536
26 1000 2097152 65536
27 1000 2097152 65536
28 1000 2097152 65536
29 1000 2097152 65536
30 1000 2097152 65536
31 1000 2097152 65536
32 1000 2097152 65536
33 1000 2097152 65536
34 1000 2097152 65536
35 1000 2097152 65536
36 1000 2097152 65536
37 1000 2097152 65536
38 1000 2097152 65536
39 1000 2097152 65536