a300. TOI 2023/10 潛力組：股票交易

題目描述

已知一檔股票連續 N 個交易日的價格 A1 到 AN。對每一天 i，假設當天以 Ai 買入一股，請找出之後最早哪一天 j 的價格至少是 Ai + K。也就是在不計額外費用時，賣出後至少能賺 K。

每一天的問題獨立計算。若後面沒有符合條件的交易日，該天的答案為 −1。

輸入格式

第一行有 N、K；第二行有 N 個整數，依序為每天的價格。

• 3 ≤ N ≤ 200000
• 1 ≤ K ≤ 1000000000
• 1 ≤ Ai ≤ 1000000000 交易日從 1 開始編號。

輸出格式

輸出一行 N 個整數，依買入日順序給出最早符合條件的賣出日；無解輸出 −1。相鄰答案以空白隔開。

來源

TOI 2023 年 10 月潛力組〈股票交易〉。題意以自寫文字重述，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202310/Stocks.pdf