問題一覧 > 通常問題

No.1698 Face to Face

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 5
作問者 : eSeFeSeF / テスター : LayCurseLayCurse 👑 ygussanyygussany
3 ProblemId : 5064 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-09-29 17:47:02

問題文

要素数 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。