CF1237B.Balanced Tunnel

普及-

通过率:0%

时间限制:1.00s

内存限制:512MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Consider a tunnel on a one-way road. During a particular day, nn cars numbered from 11 to nn entered and exited the tunnel exactly once. All the cars passed through the tunnel at constant speeds.

A traffic enforcement camera is mounted at the tunnel entrance. Another traffic enforcement camera is mounted at the tunnel exit. Perfectly balanced.

Thanks to the cameras, the order in which the cars entered and exited the tunnel is known. No two cars entered or exited at the same time.

Traffic regulations prohibit overtaking inside the tunnel. If car ii overtakes any other car jj inside the tunnel, car ii must be fined. However, each car can be fined at most once.

Formally, let's say that car ii definitely overtook car jj if car ii entered the tunnel later than car jj and exited the tunnel earlier than car jj. Then, car ii must be fined if and only if it definitely overtook at least one other car.

Find the number of cars that must be fined.

考虑一条单向道路上的隧道。在某一天,编号为 11 到 nn 的 nn 辆汽车各自恰好进入并驶出隧道一次。所有汽车均以恒定速度通过隧道。

一辆交通执法摄像头安装在隧道入口处,另一辆安装在隧道出口处。两台摄像头完美同步。

得益于这两台摄像头,我们已知汽车进入和驶出隧道的顺序。任意两辆汽车既不会同时进入,也不会同时驶出。

交通法规禁止在隧道内超车。若汽车 ii 在隧道内超越了任意其他汽车 jj,则汽车 ii 必须被罚款。但每辆汽车最多只能被罚款一次。

形式化地,我们称汽车 ii 必然超越了汽车 jj,当且仅当汽车 ii 进入隧道的时间晚于汽车 jj,且驶出隧道的时间早于汽车 jj。那么,汽车 ii 必须被罚款,当且仅当它至少必然超越了另一辆汽车。

求必须被罚款的汽车数量。

输入格式

The first line contains a single integer nn (2≤n≤1052 \le n \le 10^5), denoting the number of cars.

The second line contains nn integers a1,a2,…,ana_1, a_2, \ldots, a_n (1≤ai≤n1 \le a_i \le n), denoting the ids of cars in order of entering the tunnel. All aia_i are pairwise distinct.

The third line contains nn integers b1,b2,…,bnb_1, b_2, \ldots, b_n (1≤bi≤n1 \le b_i \le n), denoting the ids of cars in order of exiting the tunnel. All bib_i are pairwise distinct.

第一行包含一个整数 nn(2≤n≤1052 \le n \le 10^5),表示汽车的数量。

第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n(1≤ai≤n1 \le a_i \le n),表示汽车按进入隧道顺序的编号。所有 aia_i 两两不同。

第三行包含 nn 个整数 b1,b2,…,bnb_1, b_2, \ldots, b_n(1≤bi≤n1 \le b_i \le n),表示汽车按离开隧道顺序的编号。所有 bib_i 两两不同。

输出格式

Output the number of cars to be fined.

输出将被罚款的汽车数量。

输入输出样例

  • 输入#1

    5
    3 5 2 1 4
    4 3 2 5 1

    输出#1

    2
  • 输入#2

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

    输出#2

    6
  • 输入#3

    2
    1 2
    1 2

    输出#3

    0

说明/提示

The first example is depicted below:

Car 22 definitely overtook car 55, while car 44 definitely overtook cars 11, 22, 33 and 55. Cars 22 and 44 must be fined.

In the second example car 55 was definitely overtaken by all other cars.

In the third example no car must be fined.

第一个示例如下图所示:

汽车 22 必然超车了汽车 55,而汽车 44 必然超车了汽车 11、22、33 和 55。因此,汽车 22 和 44 必须被罚款。

在第二个示例中,汽车 55 必然被其余所有汽车超车。

在第三个示例中,没有汽车需要被罚款。

输入解题思路,AI测评打分。不知道怎么写?

首页