問題一覧 > 通常問題

No.1698 Face to Face

レベル : / AI推定難易度 : 2675 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 11
作問者 : eSeF / テスター : LayCurse ygussany
お気に入りにしたユーザー ProblemId : 5064 / 自分の提出
問題文最終更新日: 2021-09-29 17:47:02
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 316 (順位表) の他の問題:

Problem Statement

You are given permutations $A=(A_1,\ A_2,\ldots ,A_N),\ B=(B_1,\ B_2,\ldots ,B_N),$ and $Z=(Z_1,\ Z_2,\ldots ,Z_N)$ with $N$ elements each. That is, each of them is a rearrangement of $(1,\ 2,\ldots ,N)$.

Solve the following problem for every $k=1,2,\cdots ,N$.

Find the maximum possible score determined by the following procedure (1)–(3).

  • (1) Perform the following operation any number of times: choose an integer $i$ such that $1\le i \lt N$, $A_i\le k$, and $A_{i+1}\le k$, and swap the positions of $A_i$ and $A_{i+1}$.
  • (2) Perform the following operation any number of times: choose an integer $i$ such that $1\le i \lt N$, $B_i\le k$, and $B_{i+1}\le k$, and swap the positions of $B_i$ and $B_{i+1}$.
  • (3) The score is the number of integers $i$ that satisfy all of the following conditions.
    • $1\le i\le N$
    • In the final arrangement, let $A_x = i$ and $B_y = Z_i$. Then, $x = y$.

Input

$N$
$A_1\ \ \ldots \ \ A_N$
$B_1\ \ \ldots \ \ B_N$
$Z_1\ \ \ldots \ \ Z_N$
[Constraints]
  • $2\le N\le 10^5$
  • $A$, $B$, and $Z$ are all sequences (permutations) obtained by rearranging $(1,\ 2,\ldots ,N)$.
  • All input values are integers.

Output

Print $N$ lines. The $i$-th line should contain the answer to the problem for $k=i$.

Sample

Sample 1
Input
5
1 2 3 4 5
5 4 3 2 1
1 2 3 4 5
Output
1
1
1
3
5

When $k=1$, no elements can be moved. Therefore, the score of the initial arrangement is the maximum, and since the positions of $3$ in $A$ and $Z_3(=3)$ in $B$ coincide, the score is $1$.

When $k=4$, the score is maximized by, for example, rearranging $A$ into $(1,3,2,4,5)$ and $B$ into $(5,3,2,4,1)$, and the score in this case is $3$. This arrangement can be achieved by operations only on values less than or equal to $k=4$.

When $k=5$, it suffices, for example, to make both $A$ and $B$ equal to $(1,2,3,4,5)$, and the score is $5$.

Sample 2
Input
4
1 3 2 4
2 3 4 1
2 4 3 1
Output
4
4
4
4

Sample 3
Input
6
1 5 3 2 4 6
2 3 4 6 1 5
1 3 4 2 5 6
Output
1
1
1
1
4
6

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