定義兩個點(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
範例的操作經過處理長這樣：
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 時限稍微放寬。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||