TopCoder

柊 四千
あぅあぅ~

User's AC Ratio

64.7% (11/17)

Submission's AC Ratio

20.8% (16/77)

Tags

Description

問題敘述:
eToy 發明了一個新的益智遊戲,該遊戲由A 和B 兩人輪流在一個1,000,000x 1,000,000 的方格棋盤上的格線交點下棋,格線交點的座標以(x, y), 0 ≤ x , y ≤1,000,000 表示之,(0, 0)代表棋盤最左下角那點。

每一個棋子放置的位置不可以與任何其它棋子在同一X 座標或Y 座標上,棋盤上新增加一個棋子時,棋盤上的計數器會自動算出以目前棋盤上棋子所能夠圍成的「無障礙四方形」數。

「無障礙四方形」是指以任意兩個棋子所定義出的四方形內部不含其它棋子,每下一個棋子後所算出的「無障礙四方形」數即為下該棋子的得分數。每位下棋者的總分即是該下棋者每個棋子的得分數總和。

請寫一個程式計算A 和 B 兩位下棋者的累計總分。

Input Format

第一行輸入只有一個整數n,代表此盤棋共下了n (1 ≤ n ≤ 5,000)個棋子。接下來的n 行,每一行有兩個整數,依序代表這n 個棋子所放置的位置。

請注意,由於測試資料中確實包含n=5000 的輸入,你的程式必須非常的有效率才會通過所有的測試資料。

Output Format

請輸出兩個整數,分別代表該盤棋兩位下棋者的累計得分數。先下棋者(A)的分數在前,後下棋者(B)的分數在後,中間用一個空白隔開。

Sample Input 1

//(不包含<-以及後面的字)
4 <- 此盤棋共下了四步棋
2 3 <- 第一步棋A 下在 (2, 3) *這一步棋A 得0 分
3 4 <- 第二步棋B 下在 (3, 4) *這一步棋B 得1 分
1 2 <- 第三步棋A 下在 (1, 2) *這一步棋A 得2 分
4 1 <- 第四步棋B 下在 (4, 1) *這一步棋B 得5 分

Sample Output 1

2 6 <- 這盤棋累計得分為A 棋者2 分,B 棋者6 分

Sample Input 2

//(不包含<-以及後面的字)
7 <- 此盤棋共下了七步棋
1 5 <- 第一步棋A 下在 (1, 5) *這一步棋A 得0 分
2 7 <- 第二步棋B 下在 (2, 7) *這一步棋B 得1 分
3 8 <- 第三步棋A 下在 (3, 8) *這一步棋A 得2 分
5 1 <- 第四步棋B 下在 (5, 1) *這一步棋B 得5 分
6 2 <- 第五步棋A 下在 (6, 2) *這一步棋A 得9 分
7 3 <- 第六步棋B 下在 (7, 3) *這一步棋B 得13 分
4 4 <- 第七步棋A 下在 (4, 4) *這一步棋A 得10 分

Sample Output 2

21 19 <- 這盤棋累計得分為A 棋者21 分,B 棋者19 分

Hints

Problem Source

原TIOJ1151 / 94全國賽(prob 6)。

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 900 65536 262144 1
1 900 65536 262144 2
2 900 65536 262144 3
3 900 65536 262144 4
4 900 65536 262144 5