cswork / OA打开练习工作台

AmazonOA #123

Count Processes Giving Inaccurate Results

估计中等可在线判题

考点(AI 标注)哈希计数前缀和区间

Both arrays are permutations of 1..n, giving the prescribed order and the actual execution order respectively. When a process runs, it fails if any process prescribed before it has not run yet. A process that has already run but failed no longer counts as not yet run, so failures do not propagate.

输入格式

The first line contains n (1..200000), followed by two lines: the prescribed permutation and the actual permutation.

输出格式

Output a single integer answer.

样例 1

输入:

6
4 2 3 5 1 6
2 3 5 1 6 4

输出:

5

样例 2

输入:

3
3 2 1
3 2 1

输出:

0

样例 3

输入:

5
2 3 5 1 4
5 2 3 4 1

输出:

2

样例说明

Example 1: 4 runs last, so the other five processes all miss the prerequisite 4; the answer is 5. Example 2: the orders match, so the answer is 0. Example 3: when 5 runs, 2 and 3 are missing, and when 4 runs, 1 is missing; only these two fail, so the answer is 2.