Description:
公式日本語
N台のPCとM人の生徒がいる。(1<=N<=1000, 1<=M<=10000)
PCは誰かがログインすると、ログアウトするまで他の人がログインする事は出来ない。
生徒は何台のPCにでもログインできる。
PCの使用履歴はr行のログとして残っていて、(2<=r<=1000)
各行には、「いつ、どのPCを、誰が、ログイン/ログアウトした」という記録が記されている。
q個の「開始時刻 終了時刻 生徒番号」という形式のクエリが与えられるので、(1<=q<=50)
この時間帯にこの生徒が少なくとも1台のPCを使用していた時間の長さを求めよ。
以下のことを仮定して良い。
ログは時系列順にソートされている。
同時刻に同じPCのログは2つ以上は無い。
最初の記録の前、最後のログの後にログインされているマシンは無い。
ログに矛盾は無い。
全ての時刻は、540以上1260以下。
Answer:
本番では、N*M*全時刻にさえならなければどうやってもOK。
各クエリに対して、全てのログを順番に、何台のPCにログインしているかを計算しながら見ていけば、r*qの時間で答えを出すことが出来る。
Source: