Analyzing Login/Logout Records

時間制限 : 3 sec, メモリ制限 : 65536 KB
英語版はこちら

Problem B: ログイン/ログアウト記録の解析

あなたは大学でコンピュータ演習を担当している.大学のコンピュータシステ ムでは1日分のすべてのPCのログイン/ログアウト記録が一つのファイルに保存 されている.一人の学生は複数のPCを同時に使うことができるが,誰かがログ インして,まだログアウトしていないPCにログインすることはできない.

あなたはこのファイルを利用して特定の学生が特定の時間帯(おそらくは演習時 間)に少なくとも1台のPCを利用している時間の長さを計算するプログラムを作成する ことを頼まれた.

例えば,次のようなログイン/ログアウト記録があったとする.

  • 12:55にPC1で学生1がログイン
  • 13:00にPC4で学生2がログイン
  • 13:10にPC2で学生1がログイン
  • 13:20にPC2で学生1がログアウト
  • 13:30にPC3で学生1がログイン
  • 13:40にPC1で学生1がログアウト
  • 13:45にPC3で学生1がログアウト
  • 14:20にPC1で学生1がログイン
  • 14:30にPC4で学生2がログアウト
  • 14:40にPC1で学生1がログアウト
ここで,「13:00から14:30までの時間帯の,学生1の利用時間は」という質問が 与えられたときは,下の図のように13:00から13:45までの45分と14:20から 14:30までの10分の計55分と答える必要がある.


Input

入力はいくつかのデータセットの並びである. 入力の終わりは,一つの空白で区切られた二つのゼロからなる行で示される. データセット数が10を超えることはない.

各データセットは次のような形式をしている.

N M 
r 
利用記録1
...
利用記録r 
q 
質問1
...
質問q 

最初の行のN とM はそれぞれPC数,学生数を表す.また,r は利用記録数,q は質問数を表す.これらは次の条件を満たす整数である.

1 ≤ N  ≤ 1000, 1 ≤ M  ≤ 10000, 2 ≤ r  ≤ 1000, 1 ≤ q  ≤ 50

利用記録の各行は次のようなスペース一つで区切られた四つの整数からなる.

t  n  m  s 

s は0か1である. s が1の時は,「時刻t にPCn で学生m がログインしたこと」を表す. s が0の時は,「時刻t にPCn で学生m がログアウトしたこと」を表す. 時刻はその日の0:00からの経過を分単位で表す. t ,n , m は,次の条件を満たす.

540 ≤ t  ≤ 1260, 1 ≤ n  ≤ N , 1 ≤ m  ≤ M 

利用記録については以下を仮定してよい.

  • 記録は時刻の昇順に並んでいる.
  • 同じPCの同じ時刻の記録が二つ以上現れることはない.
  • 最初の記録以前や最後の記録以降にログインしているPCはない.
  • 同じPCについてのログインとログアウトの記録は交互に現れ,各ログイン/ログアウトの組は同じ学生のものである.

    質問の各行は次のようなスペース一つで区切られた三つの整数からなる.

    ts  te  m 

    これは,「時刻ts から時刻te までの時間帯の,学生m の利用時間は」という質問を表している. ts , te , m は,次 の条件を満たす.

    540 ≤ ts  < te  ≤ 1260, 1 ≤ m  ≤ M 

    Output

    質問ごとに,利用時間を分単位で表す十進数一つを含む1行を出力すること.出 力行には他のいかなる文字も含んではならない.

    Sample Input

    4 2
    10
    775 1 1 1
    780 4 2 1
    790 2 1 1
    800 2 1 0
    810 3 1 1
    820 1 1 0
    825 3 1 0
    860 1 1 1
    870 4 2 0
    880 1 1 0
    1
    780 870 1
    13 15
    12
    540 12 13 1
    600 12 13 0
    650 13 15 1
    660 12 15 1
    665 11 13 1
    670 13 15 0
    675 11 13 0
    680 12 15 0
    1000 11 14 1
    1060 12 14 1
    1060 11 14 0
    1080 12 14 0
    3
    540 700 13
    600 1000 15
    1000 1200 11
    1 1
    2
    600 1 1 1
    700 1 1 0
    5
    540 600 1
    550 650 1
    610 620 1
    650 750 1
    700 800 1
    0 0
    

    Output for the Sample Input

    55
    70
    30
    0
    0
    50
    10
    50
    0
    

    Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Tokyo, Japan, 2007
    http://www.logos.ic.i.u-tokyo.ac.jp/icpc2007/