読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2317 Class Representative Witch

AOJ

問題文,闇に包まれすぎ

問題文

Class Representative Witch | Aizu Online Judge
英語よりも辛いと思いますが問題文についての説明はしません()

解法

s>tが成り立つとき,区間(-s,-t)とすると,値の小さいほうが使い魔の持つ端点として統一でき,魔女の座標は0にできる.
負にする分区間を区切る点も負のものが必要になるます.

で,区間の開始点,終了点,区切る点の座標を全て一つにまとめ,何かイベントが起きる点としてソートしておきます.
区間,区切る点もそれぞれ別の配列として保存しておき,ソートしておきます.

二つのヒープを用意します.表,裏はそれぞれ明美ほむらの操作後に区間が残っているかどうかです.

  1. 今表になっている区間の終了点の集合
  1. 今裏になっている区間の終了点の集合

これらについて,イベントの若いほうから順にみていき,

  • 区間の開始点なら表のほうのヒープに終了点を追加
  • 区間の終了点なら表,裏からその終了点を持つ要素を削除
  • 区切る点なら表と裏を交換する.

を繰り返すだけでよいです.
求める長さについてですが,各イベント毎に
一つ前のイベントとの距離*表のヒープの要素数
を求めてやれば答えが出ます.
計算量は O( (N+M)log(N+M) )

ソースコード

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1898585#1
たぶんこの解法が一番楽だと思います.