yukicoder No.607 開通777年記念
解法
駅に到着するごとに条件を満たしているかを調べる必要があります.
駅に到着してからの人員の増減を配列に入れて管理し, その都度累積和を取り直します.
までの累積和のなかで2つ選ぶと, その差分を見ればその区間内の人数の和がわかります. ここで選ぶ区間の片側(右側)を固定し, 『もう一方の端をうまく選んで区間内の乗客を777人にできるか？』という問題を考えます. 累積和は単調増加であるため, いま注目している添字
に対し,
を二分探索で高速に調べることができます.
これが見つかったとき, "YES"を出力し, 見つからなかったときは最後に"NO"を出力します.
これをクエリの数回だけやるので, 全体の計算量の見積もりは
となり, この制約では間に合います.
