8VC Venture Cup 2016 - Final Round (Div. 1) C. Factory Repairs
問題設定の理解に時間がかかった。
問題概要
とある工場では一日あたり a 個の製品を作れる。しかし現在、機械が故障しているため一日あたり b 個の製品しか作れなくなっている。
このとき以下のクエリを処理せよ。
- d 日目に作るべき製品の個数を a 個増やす
- 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 ...
読めれば簡単。読めれば…。
