九州大学プログラミングコンテスト2018 D - Novelist

解法

王都から都市 $X_{i}$ へ移動する依頼をうけるとき、その後に王都から $X_{j}$ へ移動する依頼を受けるには、一旦 $X_{i}$ から王都へ戻る依頼を受ける必要があります。
ということで、王都を出て、また王都へ戻る期間を、金貨が2枚もらえる1つの区間と見て、期間が重複しないように区間を選び、もらえる金貨の枚数を最大にすることを考えます。
すると、これは区間スケジューリングと同じことを考えることになります。
さて、あとは区間を作成していけばよいのですが、作成できる全ての区間を考慮していくと、区間の個数が大きくなりすぎてしまい、時間内に解くことができなくなってしまいます。ので、王都を出発する $M$ 個の依頼について、最も効率が良くなるような、王都へ戻る依頼を $L$ 個の中から探し出し、それを1つの区間とすることで、たかだか $M$ 個の区間だけに絞ることができるようになります。
王都を出発してとある都市へ行く、 $i$ 番目の依頼について見た時、ペアとなる依頼は、

$Y_{j} = X_{i}$ および $B_{j} \gt A_{i} + T_{X_{i}}$ を満たす依頼の中で、 $B_{j}$ が最小のもの

となります。
この依頼は、 $L$ 個の依頼を、 $Y_{j}$ で分類し、それぞれ $B_{j}$ の昇順でソートしておくことで、二分探索によって求めることができます。
こうしてできたペアは、 $[A_{i},B_{j} + T_{X_{i}} ]$ という区間になります。
また、もし条件を満たすペアが存在しなかった場合、 $[A_{i}, \infty]$ という区間を作成しておきます。これは、最終的に王都に戻る必要がないので、そのパターンに対処するためです(戻れる依頼が存在する場合は、間違いなく戻った方が得をするので、この処理を行うのは、ペアとなる依頼が存在しなかった場合のみです)。
あとは、作成した区間について、区間の後ろ側で昇順ソートをし、区間スケジューリングを行っていけば答えを求めることができます。
現在、受けると決めた依頼のうち、最後に完了する時刻を $t$ とすると、ソートした区間からについて前からみていき、現在みている区間が $[X,Y]$ であったときに、