難易度評価

難易度を1〜10段階で評価できます。投票はあとから変更・取り消しできます。

難易度(投票) Lv.5.0 (2票)

投票の分布
  1. Lv.10票
  2. Lv.20票
  3. Lv.30票
  4. Lv.40票
  5. Lv.52票
  6. Lv.60票
  7. Lv.70票
  8. Lv.80票
  9. Lv.90票
  10. Lv.100票

難易度の目安を見る ↗

ログインして難易度を投票

外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

Snow and Rain

作成者 yura1685

難易度(作成者設定) Lv.5

難易度(投票) Lv.5.0 (2票)

実行時間制限
2 秒
メモリ制限
512 MiB

解説

天気を逆順に処理することを考えます。

マス vv に最後に雨が流れた日を tvt_v とすると、最終的な積雪量は tvt_v 日目より後に vv に降った雪の合計です。雨が一度も流れてこなかったマスについては、すべての日に降った雪の合計が答えになります。

雪の日には、対応する長方形領域に対して積雪量を SS 増やします。これは 2次元BIT を用いることで、長方形への加算と1点取得をそれぞれ O(log⁡Hlog⁡W)O(\log H\log W) で処理できます。

雨の日には、始点から DFS または BFS を行います。まだ訪問していないマスに到達したら、その時点でのBITの値をそのマスの答えとして確定させます。このとき、一度訪問したマスは再び探索する必要はないです(あるマスに雨が到達したら、そこから流れる先のすべてのマスにも到達できるため)。DFS・BFS 全体の計算量は O(HW)O(HW) です。

最後まで訪問されなかったマスについては、すべての雪の日の処理が終わった時点でのBITの値が答えになります。

以上より、2次元BITによる処理に O((HW+Q)log⁡Hlog⁡W)O((HW+Q)\log H\log W)、DFS・BFSが O(HW)O(HW) なので、全体の計算量は O((HW+Q)log⁡Hlog⁡W)O((HW+Q)\log H\log W) です。

ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。