大黑哥身為一個精打細算且身懷絕技的商人，在拔拔市販賣著一種獨特的商品 $Prism~Yoke$ ，由於一些不為人知的原因，這種商品不能被執法單位目擊到販賣行為(商品名稱也不能縮寫)，因此大黑哥決定使用他特製的耐重滑翔翼，藉由從高樓滑翔的方式在每棟房子的頂樓完成販賣。
拔拔市的所有房子都被建造在一條總長 $D$ 的直線上，有 $n$ 棟房子，第 $i$ 棟房子坐落在座標 $x_i$ ，高度為 $h_i$
大黑哥特製的滑翔翼讓他能在高度差不超過 $k$ ，且座標差不超過 $r$ 的高樓滑翔到低樓
也就是大黑哥能從第 $i$ 棟房子，滑翔到第 $j$ 棟房子，第 $j$ 棟房子須符合以下條件
$h_i - k \le h_j < h_i,~|x_i-x_j| \le r$
大黑哥是個自由的商人，因此他可以從任意一棟樓頂開始他的商業活動，也可以在任何一棟樓結束他的商業活動
大黑哥想知道最後以每棟樓頂，完成他的商業活動有多少種可能的路線，注意完成商業活動代表至少要有一次販賣
請將房子高度以由低到高的順序，告訴大黑哥每棟房子的答案，由於答案可能很大，請將答案 $mod~(10^9 + 7)$
第一行有四個整數 $n,D,k,r$ ，代表有 $n$ 棟房子，城市總長 $D$ ，高度差 $k$ ，座標差 $r$
接下來有 $n$ 行，每行有兩個整數 $h,x$ ，第 $i$ 行代表房子高度 $h_i$ ，座標 $x_i$
$1 \le n,k \le 2*10^5$
$1 \le D,r,x_i \le 10^9$
$h$ 是一個 $1 \sim n$ 的排列
輸出 $n$ 數字代表大黑哥以房子高度以由低到高的順序，每棟樓頂完成他的商業活動有多少種可能的路線，每個數字以空白隔開
3 5 1 1 3 1 1 2 2 3
2 1 1
子題一 $(20\%)$
$1 \le n,k \le 10^3$
$1 \le D,r,x_i \le 10^4$
子題二 $(30\%)$
$1 \le D,r,x_i \le 10^6$
子題三 $(50\%)$
題目範圍
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||