問題一覧 > 通常問題

No.318 学学学学学

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 222
作問者 : n_vip
14 ProblemId : 899 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-12-13 10:11:30

Note

この問題はAdvent Calendar Contest Advent Calendar 2015の11日目の問題として作られました。

前置き（読まなくても解けます）

豊橋技術科学大学って文字列、「大」が「学」に挟まれてるんだから豊橋技術科学学学になるべきでは？

— アレン (@chaos_phantom) 2015, 10月 23

学習院大学は学学学学学に

— (v・∇)v {εぷりん.vvv] (@mat_der_D) 2015, 10月 23
このツイートが面白いと思ったのでこれで出題します。この他にも

大学院大学は大大大大学に

— (v・∇)v {εぷりん.vvv] (@mat_der_D) 2015, 10月 23
というツイートもありました。 ただ、この場合「大」と「学」がそれぞれ2つずつあるので、どっちを先にやるかによって大大大大学にも大学学学学にもなってしまいます。
そのため、置き換える優先順位をつけることにしました。文字に優先順位をつけるのはめんどくさいので、 文字列の代わりに数列にして、数が大きい方が多く出てきやすくなるようにします。

問題文

数列 a1,…,an が与えられます。この数列を元に数列 b1,…,bn を次のように作ります。

t=1 から t=109 について、順番に次の操作をする。
al=t , ar=t であるような全ての l≤r について、bl,…,br を t で書き換える。

数列 b1,…,bn を求めて下さい。

入力

n
a1…an

1≤n≤105
1≤ai≤109

出力

b1,…,bn を空白区切りで一行に出力して下さい。

サンプル

サンプル1
入力
6
3 2 1 1 2 3
出力
3 3 3 3 3 3

便宜上{bn}が🎅で初期化されているとします。
t=1について処理をすると、数列{bn}は 🎅,🎅,1,1,🎅,🎅 となります。
t=2について処理をすると、数列{bn}は 🎅,2,2,2,2,🎅 となります。
t=3について処理をすると、数列{bn}は 3,3,3,3,3,3 となります。
t>3の操作では数列{bn}は変化しないので、答えは3,3,3,3,3,3です。

サンプル2
入力
6
3 1 10 3 10 2
出力
3 3 10 10 10 2

t=1について処理をすると、数列{bn}は 🎅,1,🎅,🎅,🎅,🎅 となります。
t=2について処理をすると、数列{bn}は 🎅,1,🎅,🎅,🎅,2 となります。
t=3について処理をすると、数列{bn}は 3,3,3,3,🎅,2 となります。
t=4,…,9では数列{bn}は変化しません。
t=10について処理をすると、数列{bn}は 3,3,10,10,10,2 となります。
t>10では数列{bn}は変化しません。

サンプル3
入力
6
1 3 10 1 10 2
出力
1 3 10 10 10 2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。