No.1698 Face to Face
タグ : / 解いたユーザー数 7
作問者 :
eSeF
/ テスター :
LayCurse
ygussany
問題文
要素数 $N$ の順列 $A=(A_1,\ A_2,\ldots ,A_N),\ B=(B_1,\ B_2,\ldots ,B_N),$ および $Z=(Z_1,\ Z_2,\ldots ,Z_N)$ が与えられます。 即ち、これらはどれも $(1,\ 2,\ldots ,N)$ の並び替えです。
$k=1,2,\cdots ,N$ の全てに対して、以下の問題を解いてください。
以下の (1)〜(3) の手順で定められるスコアの最大値を求めよ。
- (1)「$1\le i \lt N$ かつ $A_i\le k$ かつ $A_{i+1}\le k$ を満たす整数 $i$ を選んで、$A_i$ と $A_{i+1}$ の位置を入れ替える」という操作を任意の回数行う。
- (2)「$1\le i \lt N$ かつ $B_i\le k$ かつ $B_{i+1}\le k$ を満たす整数 $i$ を選んで、$B_i$ と $B_{i+1}$ の位置を入れ替える」という操作を任意の回数行う。
- (3) スコア を、以下の条件を全て満たす整数 $i$ の個数とする。
- $1\le i\le N$
- 最終的な並びにおいて、$A_x = i$、 $B_y = Z_i$ であるとする。 このとき、$x = y$ である。
入力
$N$ $A_1\ \ \ldots \ \ A_N$ $B_1\ \ \ldots \ \ B_N$ $Z_1\ \ \ldots \ \ Z_N$【制約】
- $2\le N\le 10^5$
- $A$、$B$、$Z$ は全て $(1,\ 2,\ldots ,N)$ を並び替えてできる数列（順列）である。
- 入力は全て整数
出力
$N$ 行出力し、$i$ 行目には $k=i$ の場合の問題の答えを出力せよ。
サンプル
サンプル1
入力
5 1 2 3 4 5 5 4 3 2 1 1 2 3 4 5
出力
1 1 1 3 5
$k=1$ のとき、要素を動かすことはできません。したがって、初期配置におけるスコアが最大であり、 $A$ の $3$ と $B$ の $Z_3(=3)$ の位置が一致しているのでスコアは $1$ です。
$k=4$ のとき、例えば $A$ を $(1,3,2,4,5)$、$B$ を $(5,3,2,4,1)$ と並び替えることでスコアが最大になり、 このときスコアは $3$ です。$k=4$ 以下の値のみに対する操作によってこの配置は実現可能です。
$k=5$ のときは、例えば $A$ と $B$ を共に $(1,2,3,4,5)$ にすれば良く、スコアは $5$ です。
サンプル2
入力
4 1 3 2 4 2 3 4 1 2 4 3 1
出力
4 4 4 4
サンプル3
入力
6 1 5 3 2 4 6 2 3 4 6 1 5 1 3 4 2 5 6
出力
1 1 1 1 4 6
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。