codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1237B.md (2216B)


      1 Source: https://codeforces.com/problemset/problem/1237/B
      2 
      3 B. Balanced Tunnel
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Consider a tunnel on a one-way road. During a particular day, $n$ cars numbered from $1$ to $n$ entered and exited the tunnel exactly once. All the cars passed through the tunnel at constant speeds.
     22 
     23 A traffic enforcement camera is mounted at the tunnel entrance. Another traffic enforcement camera is mounted at the tunnel exit. Perfectly balanced.
     24 
     25 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.
     26 
     27 Traffic regulations prohibit overtaking inside the tunnel. If car $i$ overtakes any other car $j$ inside the tunnel, car $i$ must be fined. However, each car can be fined at most once.
     28 
     29 Formally, let's say that car $i$ definitely overtook car $j$ if car $i$ entered the tunnel later than car $j$ and exited the tunnel earlier than car $j$. Then, car $i$ must be fined if and only if it definitely overtook at least one other car.
     30 
     31 Find the number of cars that must be fined.
     32 
     33 Input
     34 
     35 The first line contains a single integer $n$ ($2 \le n \le 10^5$), denoting the number of cars.
     36 
     37 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$), denoting the ids of cars in order of entering the tunnel. All $a_i$ are pairwise distinct.
     38 
     39 The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le n$), denoting the ids of cars in order of exiting the tunnel. All $b_i$ are pairwise distinct.
     40 
     41 Output
     42 
     43 Output the number of cars to be fined.
     44 
     45 Examples
     46 
     47 Input
     48 
     49 ```
     50 5
     51 3 5 2 1 4
     52 4 3 2 5 1
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 2
     59 ```
     60 
     61 Input
     62 
     63 ```
     64 7
     65 5 2 3 6 7 1 4
     66 2 3 6 7 1 4 5
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 6
     73 ```
     74 
     75 Input
     76 
     77 ```
     78 2
     79 1 2
     80 1 2
     81 ```
     82 
     83 Output
     84 
     85 ```
     86 0
     87 ```
     88 
     89 Note
     90 
     91 The first example is depicted below:
     92 
     93 ![](https://espresso.codeforces.com/b8f505b38707f87ac16773bccb0b71793cba0965.png)
     94 
     95 Car $2$ definitely overtook car $5$, while car $4$ definitely overtook cars $1$, $2$, $3$ and $5$. Cars $2$ and $4$ must be fined.
     96 
     97 In the second example car $5$ was definitely overtaken by all other cars.
     98 
     99 In the third example no car must be fined.