apples - リンゴの出荷 (Apples) Editorial /

Time Limit: 4 sec / Memory Limit: 256 MiB

配点 : 100 点

問題文

JOI 農場ではリンゴの入荷と出荷を行っている.JOI 農場は 1 つずつリンゴを入荷し,出荷依頼が来た場合は次の入荷を待たずに対応を行う.出荷依頼では出荷するリンゴの個数が指定されており,JOI 農場は出荷依頼が来た時,出荷依頼で指定されている個数のリンゴを,JOI 農場の決まりを満たす組み合わせで出荷できる場合,すぐにそれらのリンゴを出荷する.一方,出荷できない場合は,出荷できないことを伝えリンゴは全く出荷しない.

今年は JOI 農場に多くのリンゴの入荷と多くの出荷依頼が来ることが見込まれている.そこで,あなたに JOI 農場のためのリンゴ管理プログラムを書いて欲しい.

課題

各々のリンゴには色の濃さが整数値で決まっている.1 回の出荷におけるリンゴの濃さのバラつきとは,出荷されるリンゴの濃さの最大値と最小値の差である.JOI 農場では各出荷依頼について,濃さのバラつきが B 以下でなければならない,という決まりがある.

JOI 農場が行うリンゴ管理プログラムへは合計 M 個の要求が行われる.i 番目の要求は「リンゴの入荷」「出荷依頼」「プログラムの終了」の 3 種類のうちのいずれかである.それぞれの要求に対し,リンゴ管理プログラムは以下の動作をしなければならない.

  • 「リンゴの入荷」の要求に対しては,濃さの値が D_{i} のリンゴを 1 個入荷したことが入力されるので,これを記憶する.
  • 「出荷依頼」の要求に対しては,N_{i} 個のリンゴを出荷する出荷依頼が来たことが入力されるので,出荷できる場合は出荷するリンゴの濃さの値をそれぞれ昇順に出力し,出荷できない場合は NO を出力する.ただし,出荷するリンゴの組み合わせの候補が複数存在する場合は,リンゴの色の濃さの値の総和が最も大きくなる組み合わせを選択する.
  • 「プログラムの終了」の要求に対しては,リンゴ管理プログラムの終了命令が入力されるので,プログラムを終了する.

注意

この課題は応答型課題 (Reactive task) である.i 番目の要求が「出荷依頼」である場合,i + 1 番目の要求の入力は i 番目の出荷依頼に対する出力をした後に与えられる.

また,出力がバッファされ,読み込みが誤ってブロックされてしまうことを防ぐ必要がある.そのため読み込みを行う前に fflush(stdout); などを記述しておくことを勧める.

制約

  • 1 \leqq M \leqq 100\,000:プログラムに渡される要求の数.
  • 0 \leqq B \leqq 1\,000\,000\,000:各出荷毎のリンゴの濃さのバラつきの上限値.
  • 0 \leqq D_i \leqq 1\,000\,000\,000\ {} (1 \leqq i \leqq M):i 番目の要求で入荷するリンゴの色の濃さの値.
  • 1 \leqq N_i \leqq 100\,000\ {} (1 \leqq i \leqq M):i 番目の要求で出荷するリンゴの個数.

入力

標準入力から以下の入力を読み込め.

  • 1 行目には整数 M, B が空白を区切りとして書かれており,要求の個数が M 個,JOI 農場の決まりである,リンゴの濃さのバラつきの上限値が B であることを表す.
  • 1 + i 行目 (1 \leqq i \leqq M - 1) には「リンゴの入荷」「出荷依頼」のどちらかの要求を示す情報が書かれている.

    • i 番目の要求が「リンゴの入荷」である場合,文字 A と,入荷したリンゴの色の濃さの値を表す整数 D_{i} が空白を区切りとして書かれている.
    • i 番目の要求が「出荷依頼」である場合,文字 R と,出荷依頼の依頼内容である出荷するリンゴの個数を表す整数 N_{i} が空白を区切りとして書かれている.
  • 1 + M 行目には「プログラムの終了」の要求を表す文字 E のみが書かれている.

出力

各「出荷依頼」の要求を受けた時に,出荷できない場合は文字列 NO を 1 行で出力せよ.出荷できる場合は,出荷するリンゴの色の濃さを昇順で空白を区切りとして 1 行に出力せよ.

採点基準

採点用データのうち,配点の 30\% 分については,B \leqq 10\,000 かつ D_{i} \leqq 10\,000 (1 \leqq i \leqq M) を満たす.

入出力の例

入力例

22 10
A 5
A 16
R 2
A 10
R 2
R 2
A 15
A 5
R 2
A 5
R 2
A 0
A 10
R 1
A 10
A 10
R 4
A 30
R 4
A 0
R 4
E

出力例

NO
10 16
NO
5 15
5 5
10
NO
NO
0 0 10 10

Source Name

JOI 2010-2011 日本代表選手選考会 Contest Day4