e096. Emilia's story - 2 Bright Stars - 高中生程式解題系統

內容

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

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

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

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

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

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

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

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

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

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

輸入說明

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

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

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

輸出說明

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

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

範例輸入 #1

範例輸出 #1

(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

提示：

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

標籤:

kd樹

出處:

Emilia's story [管理者： emiliaistruelove@gmail.com

qqrainbow (愛蜜莉雅) ]

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