No testdata at current.

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

🧠 題目名稱：橫置神樹守衛戰

📝 題目背景：

在遙遠的古代，有一棵被橫置於平原上的神樹，其樹節點上安置著強大的防禦塔。這些塔各自擁有攻擊力、攻擊範圍、高度與攻擊間隔等屬性，能對從樹下通過的入侵者進行打擊。

你被指派模擬這場防守行動，確保在給定的時間與條件下，計算每一名動態入侵的人類是否能夠活著穿越整個區域。

---

🌳 結構說明：

神樹是一棵 二叉樹，橫置在 X 軸上，根節點在最左邊（x=0），每向下一層，子節點位於其左或右子樹之上（x座標遞增），所有塔的 y 座標即為其「高度」。

每個塔節點包含以下屬性：

• 攻擊力 d
• 攻擊範圍 r：可以攻擊位於以塔為圓心，半徑為 r 的圓內的單位
• 攻擊間隔 t：每隔 t 單位時間可攻擊一次
• 高度 h：塔的 y 座標，入侵者 y 座標固定為 0

---

👾 模擬說明：

人類會在時間 t=0 開始陸續登場，每個人類會：

• 以速度 v 沿 x 軸從 x=0 開始移動（y=0）
• 每人具有初始 HP 值 hp
• 可以與其他人類重疊
• 當其 HP ≤ 0 時死亡，不再移動

系統將根據輸入模擬至時間 T，對於每一名人類，輸出其是否成功穿越了攻擊區（即走到 x > max_x）。

---

🎯 任務說明：

請你模擬整個過程，對於每一名人類，判斷是否能夠生存並穿越神樹的攻擊範圍。

---

📥 輸入格式：

第一行一個整數 n（1 ≤ n ≤ 10⁵）：表示塔的節點數量 接下來 n 行，每行描述一個節點：

id l r d r t h

• id：節點編號（1-based）
• l, r：左子節點與右子節點的編號（若無則為 0）
• d：攻擊力
• r：攻擊範圍
• t：攻擊間隔
• h：塔高度

再下一行一個整數 Q（1 ≤ Q ≤ 10⁵）：表示人類進入的總次數

接下來 Q 行，每行表示一名人類的資訊：

T_enter v hp

• T_enter：該人類進入模擬的時間點
• v：移動速度（整數，每單位時間移動 v 單位距離）
• hp：血量（整數）

---

📤 輸出格式：

對於每一名人類，輸出一行：

YES

若能安全通過，否則輸出：

NO

---

🔎 額外說明：

• 所有座標都在整數點上
• 所有塔永遠不會移動
• 所有塔會在每個時間點進行攻擊（若滿足攻擊間隔），攻擊會即時造成傷害
• 每次攻擊若有多名人類在攻擊範圍內，每人都會受到該塔的完整傷害
• 所有攻擊與移動都同步進行
• 若某人類在被攻擊當刻死亡，該刻之後不再移動也不再被攻擊

---

📘 樣例輸入：

3
1 2 3 10 5 2 3
2 0 0 5 3 1 2
3 0 0 7 4 1 4
2
0 1 50
3 2 20

📗 樣例輸出：

YES
NO

---

🧠 提示與知識點：

• 模擬類題目可透過「事件排序 + 優先隊列 + 時間軸」處理高效模擬
• 如何建立橫向座標：你可用 BFS 或 DFS 給每個節點設置 x 座標
• 空間優化考慮：不必對每個時間點模擬整個平面，可僅記錄每位人類當前位置與下次受攻時間
• 可使用區間樹或KD-Tree進行空間查找優化（進階解法）