Apples(リンゴの出荷) - joi2011-day4

出典: 第10回日本情報オリンピック 日本代表選手選考会

時間制限: 4秒

メモリ制限: 256MB

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

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

課題

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

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

注意

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

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

制限

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

入力

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

出力

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

採点基準

入出力の例

入力例 出力例
22 10
A 5
A 16
R 2
NO
A 10
R 2
10 16
R 2
NO
A 15
A 5
R 2
5 15
A 5
R 2
5 5
A 0
A 10
R 1
10
A 10
A 10
R 4
NO
A 30
R 4
NO
A 0
R 4
0 0 10 10
E