pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

8VC Venture Cup 2016 - Final Round (Div. 1) C. Factory Repairs

問題設定の理解に時間がかかった。

codeforces.com

問題概要

とある工場では一日あたり a 個の製品を作れる。しかし現在、機械が故障しているため一日あたり b 個の製品しか作れなくなっている。

このとき以下のクエリを処理せよ。

  1. d 日目に作るべき製品の個数を a 個増やす
  2. p 日目に修理を行ったとき、n 日間で作れる最大の製品数を出力する

なお修理には k 日間かかり、その最中は一切製造できない。修理が終われば正常通り一日に a 個の製品を作れるようになる。

解法

故障時と正常時それぞれに対して、[l,r) の期間に作れる最大の製品数を求められれば、

  • 故障時[0,p)+正常時[p+k,n)

で答えが求まる。

高速に計算するには葉ノードの値の上限を a あるいは b とする総和のセグ木を作ればいい。

Submission #16411814 - Codeforces

8VC Venture Cup 2016 - Final Round (Div. 1) C. Fac ...

読めれば簡単。読めれば…。