TopCoder

Thumb
柊 四千
あぅあぅ~

User's AC Ratio

70.0% (7/10)

Submission's AC Ratio

34.5% (10/29)

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 分

輸入範例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

輸出範例1:
2 6 <- 這盤棋累計得分為A 棋者2 分,B 棋者6 分

輸出範例2:
21 19 <- 這盤棋累計得分為A 棋者21 分,B 棋者19 分

Hints

Problem Source

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

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 900 65536 262144
1 900 65536 262144
2 900 65536 262144
3 900 65536 262144
4 900 65536 262144