Description:
N頭の牛が整列していて、一番背の高い牛の番号Iと、その背の高さHがわかっている。(1<=N<=1万, 1<=H<=100万)
更に、R個の、「牛Aが牛Bを見る事が出来る」という形の条件が与えられる。(0<=R<=1万)
この条件は、Bの背の高さが、A以上で、AとBの間の全ての牛の背の高さは、A未満だという事を意味している。
各牛の背の高さの最大値を求めよ。
Answer:
条件を良く見ると、条件同士の範囲は、他方が完全に他方を含まない形ではオーバーラップしないという事に気づく。
これにより、ある条件に囲まれている範囲は、条件の両端の牛の背の高さが決まっていれば、条件範囲外の牛の背の高さと無関係に決めることが出来るという事がわかる。
これより、出来るだけ大きく牛を囲っている条件から処理をして、一つ内側の条件に含まれない部分の背の高さは外側の両端の牛の背の高さの低い方-1と、背の高さが不確定な領域をどんどん狭めていく事で答えを求めることが出来る。
番号1, N-1の牛の背の高さは必ずHとなり、「一番背の高い牛の番号I」は使用しない。
Source: