e096: Emilia's story - 2 Bright Stars
Tags : kd樹
Accepted rate : 4人/7人 ( 57% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-07-05 22:23

Content

時間來到15歲的某個夏夜,

妳與莉雅一同躺在床上,看著玻璃天花板後的璀燦星空。

映照在虹膜上的星空比煙火更璀璨,比幽暗更加幽暗,宛如天神把鬱藍顏料灑落畫布般。

映入心中的星空,就連七彩的霓虹都感到無力燦爛。

星空中每一顆星星都是一個不同的世界,在那即將消逝的星星,有過怎樣的世界、那即將誕生的星星,將刻出怎樣的故事?

是相戀的盛櫻、亦或是即將凋零的火花。

轉瞬間,妳與莉雅互相依偎著掉入了夢中無盡璀麗的星群。

圖源: https://www.pixiv.net/member_illust.php?mode=medium&illust_id=66756315

---------------------------------------------------------

請求出以(x,y,z)為中心,第k近的星星曼哈頓距離為何?

 

Input

第一行有一個正整數$n$,代表接下來有對於$n$顆星星的操作。

每筆操作包含4個整數$op$, $x$, $y$, $z$,分別代表操作、以及座標。

$op \in {0, 1, 2}$
$0$ 代表查詢,此時後面會再接一個正整數$k$,代表查詢以座標$(x, y, z)$為中心,第$k$近星星的距離;
$1$ 代表有一顆星星誕生在$(x, y, z)$;
$2$ 代表有一顆在$(x, y, z)$的星星消殞了(如果不存在這顆星星,請忽略這個操作)。

Output

對於每次查詢,請輸出第$k$近星星的*曼哈頓*距離,如果沒有請輸出"(not found)"

妳必須對每個查詢進行在線操作。

Sample Input
8
0 0 0 0 2
1 1 1 1
1 1 1 2
0 0 0 0 2
0 0 0 0 1
1 1 3 1
2 1 1 2
0 0 0 0 2
Sample Output
(not found)
(4)
(3)
(5)
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (16%): 0.5s , <1K
公開 測資點#1 (16%): 0.5s , <1K
公開 測資點#2 (17%): 0.5s , <1K
公開 測資點#3 (17%): 1.0s , <10M
公開 測資點#4 (17%): 1.5s , <10M
公開 測資點#5 (17%): 2.0s , <50M
Hint :

$x, y, z \leq 150000$、$N \leq 92300 * 5$、$1 \leq k \leq 150$

:)

Tags:
kd樹
出處:
Emilia's story [管理者:
qqrainbow (愛蜜莉雅 準•學測戰士)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」