c535: 動態曼哈頓最短距離
標籤 :
通過比率 : 46% (6 人 / 13 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-04-10 12:39

內容

定義兩個點(x,y) 和 (a,b) 的曼哈頓距離為 |x-a| + |y-b| 。

 

現在,你有一個點集S,一開始為空,請你支援兩種操作

1. 加入:把一個點 (x,y) 加入點集S中。

2. 查詢:如果這時點集為空,輸出0。否則,輸出 (x,y) 與點集S裡面所有點的曼哈頓距離的最小值。

 

 

輸入說明

輸入的第一行有一個整數Q (1 <= Q <= 200000),代表操作筆數。

現在定義 last_ans = 0

接下來的Q行,每行有三個正整數 c, x, y (c == 1 or c==2, 1 <= x,y <= 10^8)

在做任何操作之前,請先執行 x = (last_ans + x) % 10^8 + 1, y = (last_ans + y) % 10^8 + 1

若 c==1,代表加入操作,請你把(x,y)加入到點集S裡面。

若 c==2,代表查詢操作,如果這時點集為空,輸出0。否則,輸出 (x,y) 與點集S裡面所有點的曼哈頓距離的最小值。並且把 last_ans 設成 這筆查詢的答案。

輸出說明

對於每筆查詢操作,請輸出一行題目敘述要求的值於一行。

範例輸入
6
2 1 1
1 1 1
2 2 2
1 1 1
2 4 4
2 100 100
範例輸出
0
2
6
206
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (16%): 0.5s , <1M
公開 測資點#1 (16%): 0.5s , <1M
公開 測資點#2 (17%): 3.0s , <10M
公開 測資點#3 (17%): 3.0s , <10M
公開 測資點#4 (17%): 6.5s , <10M
公開 測資點#5 (17%): 8.0s , <10M
提示 :

範例的操作經過處理長這樣:

6

2 2 2

1 2 2

2 3 3

1 4 4

2 7 7

2 107 107

 

對於第一筆詢問,因為這時點集S沒有任何點,所以輸出0。

對於第二筆詢問,此時點集S裡面有(2,2)這個點,min( |3-2| + |3-2| ) = 2

對於第三筆詢問,此時點集S裡面有(2,2),(4,4)這兩個點,min( |7-2| + |7-2| , |7-4| + |7-4| ) = 6

對於第三筆詢問,此時點集S裡面有(2,2),(4,4)這兩個點,min( |107-2| + |107-2| , |107-4| + |107-4| ) = 206

 

測資範圍:

第一筆(16%):Q = 1000

第二筆(16%):Q = 1000

第三筆(17%):Q = 100000

第四筆(17%):Q = 100000

第五筆(17%):Q = 200000

第六筆(17%):Q = 200000

 

時限卡的有點緊,如果複雜度是對的卻TLE的話,請想辦法壓常數 >__< 。

比如說,盡量不要使用很慢的函式.........等等。

 

update: 2018/03/06 16:55 時限稍微放寬。

update: 2018/03/06 17:38 記憶體限制在Zerojudge最大只能開到512MB,如果時間複雜度是對的話,請盡量的壓記憶體,MLE在Zerojudge上面會顯示RE。

update: 2018/04/10 11:00 修正範例解釋之錯誤,感謝WayneTu告知。

update: 2018/04/10 12:38 時限稍微放寬。

標籤:
出處:
[編輯:
yp155136 (meruru~)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」