TLE '17 Contest 3 P2 - Sectors

View as PDF

Submit solution


Points: 3 (partial)
Time limit: 0.3s
Java 1.0s
Python 1.0s
Memory limit: 256M

Author:
Problem type
Fax McClad deep within the Dankey Kang Gang hideout.

Fax McClad, Croneria's most overpowered bounty hunter, has infiltrated the Dankey Kang Gang hideout!

The hideout contains S sectors, numbered from 1 to S. Fax must visit K sectors for various reasons, such as confiscating goods, or defeating henchmen. The i^\text{th} sector that he must visit is sector a_i. Note that Fax might have to visit a sector more than once.

The S sectors are connected in a single straight line. The j^\text{th} sector in the line is sector number s_j. It is guaranteed that s_x \ne s_y if x \ne y. Fax starts at the first sector he needs to visit and is only allowed to travel to sectors connected to the current one that he is in. That is, if Fax is in sector s_k, he can only go to sector s_{k-1} or s_{k+1}, if they exist. Note that sectors s_1 and s_S are not connected if S > 2.

Fax wants to visit the K sectors in order, while going through a minimal number of sectors. This count is increased by one every time Fax walks through a sector, regardless if he has already went through it or not.

Can you tell him the minimum number of times that he must go through a sector?

Input Specification

The first line will contain S (1 \le S \le 10^5) and K (1 \le K \le 10^5).

S lines of input will follow. The j^\text{th} line will contain s_j.

K lines of input will follow. The i^\text{th} line will contain a_i.

For 50\% of the points, 1 \le S,K \le 10^3.

It is recommended to use 64-bit integers (long long in C++, int64 in Pascal, long in Java) when computing the answer.

Output Specification

Output a single integer, the minimum number of times he must go through a sector.

Sample Input 1

4 4
1
2
3
4
1
4
2
3

Sample Output 1

7

Explanation for Sample Output 1

Fax can go through the sectors in the following order: 1, 2, 3, 4, 3, 2, 3. Therefore, he went through 7 sectors.

Sample Input 2

4 4
2
3
1
4
1
4
2
3

Sample Output 2

6

Comments

There are no comments at the moment.