c571. 三維偏序問題 - 高中生程式解題系統

內容

給出一個三維空間的點集 $P$ (不保證點相異)，請問對於第 $i$ 個點，能從 $P$ 裡面找出多少點同時滿足 $x_{j} > x_{i}, y_{j} > y_{i} 和 z_{j} > z_{i}$ ?

輸入說明

第一行為一正整數 $N (1 \leq N \leq 100000)$ ，代表集合中的點數。

接下來的 $N$ 行分別有三個正整數 $x_{i}, y_{i}, z_{i} (1 \leq x_{i}, y_{i}, z_{i} \leq N)$ ，表示第 $i$ 個點的座標。

輸出說明

對於第 $i$ 行，輸出第 $i$ 個點的答案。

範例輸入 #1

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (10%): 1.0s , <1M
公開測資點#1 (10%): 1.0s , <1M
公開測資點#2 (10%): 1.0s , <10M
公開測資點#3 (10%): 1.0s , <10M
公開測資點#4 (10%): 1.0s , <10M
公開測資點#5 (10%): 1.0s , <10M
公開測資點#6 (10%): 1.0s , <10M
公開測資點#7 (10%): 1.0s , <10M
公開測資點#8 (10%): 1.0s , <10M
公開測資點#9 (10%): 1.0s , <10M

提示：

以第一行範例輸出為例， (8, 7, 8) 是唯一符合 (x > 7, y > 2, z > 6) 的點。

對於 20% 測資， $N \leq 1000$ 。

對於 30% 測資， $x_{i} = y_{i}$ 。

對於 50% 測資， $N \leq 100000$ 。

標籤:

CDQ 分治

出處:

[管理者： icube (!@#$%^&*()_...) ]

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