prithivMLmods/Coder-Stat

1 2 3 4<H1>勉強会</H1>5<p>6プログラマー養成校のアカベ高校には、生徒自身で運営するユニークな勉強会があります。プログラマーは新しい技術を常に取り入れることが大切なので、この勉強会を通して自学自習の習慣を身につけることがこの活動のねらいです。7</p>8 9<p>10生徒は全部で<var>N</var>人おり、それぞれが入学時のプログラミングコンテストの結果で得られたスコアを持っています。勉強会では<var>N</var>人の生徒のうち何人かがリーダーになり、各リーダーがそれぞれのグループを運営するとともに、自らの運営するグループに参加します。11</p>12 13<p>14リーダー以外の生徒は、自分のスコアよりも低いスコアのリーダーが運営するグループには参加できません。また、0以上のある値<var>r</var>を１つ決め、グループに参加する生徒とリーダーのスコアの差が<var>r</var>以内となるようにしています。つまり、グループのリーダーのスコアが<var>s</var>のとき、自分のスコアが<var>s</var>を超えているか、あるいは <var>s</var> - <var>r</var> 未満ならば、そのグループには参加できません。15</p>16 17<p>18あなたは勉強会の実行委員長であり、運営準備のためにシミュレーションを行うことにしました。シミュレーションでは、リーダーが誰もいない状態から始め、以下の操作を何回か繰り返します。19</p>20<ul>21<li> 生徒をリーダーに加える。</li>22<li> 生徒をリーダーから外す。</li>23<li> 要求時点でのリーダーの組み合わせについて、どのグループにも参加できない生徒が<var>x</var>人以下になるような、最小の<var>r</var>を求める。</li>24</ul>25 26<p>27このようなシミュレーションを行うプログラムを作成してください。28</p>29 30<h2>入力</h2>31 32<p>33入力は1つのデータセットからなる。入力は以下の形式で与えられる。34</p>35 36<pre>37<var>N</var> <var>Q</var>38<var>s<sub>1</sub></var>39<var>s<sub>2</sub></var>40:41<var>s<sub>N</sub></var>42<var>QUERY<sub>1</sub></var>43<var>QUERY<sub>2</sub></var>44:45<var>QUERY<sub>Q</sub></var>46</pre>47 48<p>491行目に生徒の数<var>N</var>(1 &le; <var>N</var> &le; 1000000)、処理要求の数<var>Q</var>(0 &le; <var>Q</var> &le; 1000)が与えられる。50</p>51 52<p>53続く<var>N</var>行に<var>i</var>番目の生徒のスコアを示す整数<var>s<sub>i</sub></var>(0 &le; <var>s<sub>i</sub></var> &le; 1,000,000,000)が与えられる。生徒は1,2,...,<var>N</var> で番号付けされているものとする。54</p>55 56<p>57続く<var>Q</var>行に処理要求<var>QUERY<sub>i</sub></var>が与えられる。処理要求は時系列順に与えられる。処理要求はADD, REMOVE, CHECKの3種類あり、各<var>QUERY<sub>i</sub></var>は以下のいずれかの形式で与えられる。58</p>59 60<pre>61ADD <var>a</var>62</pre>63 64<p>65または66</p>67 68<pre>69REMOVE <var>a</var>70</pre>71 72<p>73または74</p>75 76<pre>77CHECK <var>x</var>78</pre>79 80<p>81ADD <var>a</var>は番号<var>a</var>(1 &le; <var>a</var> &le; <var>N</var>)の生徒をリーダーに加えることを表す。82</p>83 84<p>85REMOVE <var>a</var>は番号<var>a</var>(1 &le; <var>a</var> &le; <var>N</var>)の生徒をリーダーから外すことを表す。86</p>87 88<p>89CHECK <var>x</var>は出力要求を表す。どのグループにも参加できない生徒の数の上限<var>x</var>(0 &le; <var>x</var> &le; <var>N</var>)が与えられる。90</p>91<p>92なお、入力は以下の条件を満たすものとする。93</p>94<ul>95<li> どの時点でも、リーダーの人数が100人を超えることはない。</li>96<li> その時点でリーダーである生徒をリーダーに加えることはない。</li>97<li> その時点でリーダーでない生徒をリーダーから外すことはない。</li>98</ul>99 100 101 102 103<h2>出力</h2>104 105<p>106時系列順に各出力要求の時点で、どのグループにも参加できない生徒がx人以下になるような最小の<var>r</var>を1行に出力する。ただし、どのような<var>r</var>を選んでも<var>x</var>人以下にすることが不可能であればNAと出力する。107</p>108 109<h2>入力例 1</h2>110 111<pre>1125 8113511410115811671173118ADD 1119ADD 3120CHECK 0121CHECK 1122CHECK 2123CHECK 3124CHECK 4125CHECK 5126</pre>127 128 129<h2>出力例 1</h2>130 131<pre>132NA13321341135013601370138</pre>139 140<br/>141 142<h2>入力例 2</h2>143 144<pre>1455 28146514710148814971503151CHECK 0152CHECK 1153CHECK 2154CHECK 3155CHECK 4156CHECK 5157ADD 1158CHECK 0159CHECK 1160CHECK 2161CHECK 3162CHECK 4163CHECK 5164REMOVE 1165ADD 3166CHECK 0167CHECK 1168CHECK 2169CHECK 3170CHECK 4171CHECK 5172ADD 1173CHECK 0174CHECK 1175CHECK 2176CHECK 3177CHECK 4178CHECK 5179</pre>180 181 182<h2>出力例 2</h2>183 184<pre>185NA186NA187NA188NA189NA1900191NA192NA193NA194219501960197NA19851993200120102020203NA20422051206020702080209</pre>