問題一覧 > 通常問題

No.1460 Max of Min

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 23
作問者 : shiomusubi496shiomusubi496 / テスター : butsurizukibutsurizuki
15 ProblemId : 6135 / 出題時の順位表
問題文最終更新日: 2021-04-03 09:29:59

注意

この問題は実行時間制限が厳しいので高速な言語を使用することを推奨します。(writer解はPython3ではTLE、PyPy3ではACすることを確認しています。)

問題文

長さ $K$ の正整数列 $B$ が与えられます。ここで、数列 $A$ を次のように定義します。

  • $A_0, A_1, A_2, ... A_{K-1}$ は与えられる
  • $K\leq i$ の任意の $i$ について、 $A_i=max(min(A_{i-K},B_0),min(A_{i-K+1},B_1),min(A_{i-K+2},B_2), ... min(A_{i-1},B_{K-1}))$
$N$ が与えられるので、 $A_N$ を求めて下さい。

入力

$K\ N$
$A_0\ A_1\ A_2\cdots A_{K-1}$
$B_0\ B_1\ B_2\cdots B_{K-1}$
  • $1\leq K\leq 1000$
  • $0\leq N\leq 10^{18}$
  • $-10^{18}\leq A_i\leq 10^{18}$
  • $-10^{18}\leq B_i\leq 10^{18}$
  • 入力は全て整数

出力

$A_N$ を一行に出力し、最後に改行してください。

サンプル

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

数列 $A$ は次のようになります。

$A_0=3$
$A_1=1$
$A_2=max(min(3,4),min(1,2))=3$
$A_3=max(min(1,4),min(3,2))=2$

よって $A_3=2$ なので、 $2$ を出力します。

サンプル2
入力
1 1000
6
8
出力
6

$A$ の要素は全て $6$ です。

サンプル3
入力
5 10
4390 3289 3280 8032 5814
8231 9107 3289 4361 1332
出力
4390

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