306464: CF1201D. Treasure Hunting
Memory Limit:256 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Treasure Hunting
题意翻译
题目描述 有一个$n*m$的矩阵,行的标号从$1$到$n$,列的标号从$1$到$m$,矩阵中共有$k$个宝藏,第$i$个宝藏的位置为$(r_i,c_i)$。有$q$个安全的列,第$i$个安全的列的编号是$b_i$。 最初你站在矩阵的左下角(也就是$(1,1)$的位置),并且可以向左走(从$(r,c)$到$(r,c-1)$)和向右走(从$(r,c)$到$(r,c+1)$)。同时,你也可是向上走(从$(r,c)$到$(r+1,c)$),但是你必须在安全的列上。由于某些玄学原因,你不可以向下走。 你的任务是收集所有的宝藏,但是你的时间已经不多了,所以你必须走最快的路径。现在你要使用你的人脑大法来计算出最快的路径需要多少时间(经过有宝藏的格子时收集宝藏不消耗时间,只有移动消耗时间)。 输入格式 第一行为四个整数$n,m,k,q(2≤n,m,k,q≤2*10^5,q≤m)$——行数,列数,宝藏个数,安全的列的个数。 接下来$k$行每行两个整数$r_i,c_i(1≤r_i≤n,1≤c_i≤m)$——宝藏的位置。 最后一行为$q$个整数$b_1,b_2,...,b_q$——安全的列的编号。 输出格式 一个整数,最快的路径需要的时间。题目描述
You are on the island which can be represented as a $ n \times m $ table. The rows are numbered from $ 1 $ to $ n $ and the columns are numbered from $ 1 $ to $ m $ . There are $ k $ treasures on the island, the $ i $ -th of them is located at the position $ (r_i, c_i) $ . Initially you stand at the lower left corner of the island, at the position $ (1, 1) $ . If at any moment you are at the cell with a treasure, you can pick it up without any extra time. In one move you can move up (from $ (r, c) $ to $ (r+1, c) $ ), left (from $ (r, c) $ to $ (r, c-1) $ ), or right (from position $ (r, c) $ to $ (r, c+1) $ ). Because of the traps, you can't move down. However, moving up is also risky. You can move up only if you are in a safe column. There are $ q $ safe columns: $ b_1, b_2, \ldots, b_q $ . You want to collect all the treasures as fast as possible. Count the minimum number of moves required to collect all the treasures.输入输出格式
输入格式
The first line contains integers $ n $ , $ m $ , $ k $ and $ q $ ( $ 2 \le n, \, m, \, k, \, q \le 2 \cdot 10^5 $ , $ q \le m $ ) — the number of rows, the number of columns, the number of treasures in the island and the number of safe columns. Each of the next $ k $ lines contains two integers $ r_i, c_i $ , ( $ 1 \le r_i \le n $ , $ 1 \le c_i \le m $ ) — the coordinates of the cell with a treasure. All treasures are located in distinct cells. The last line contains $ q $ distinct integers $ b_1, b_2, \ldots, b_q $ ( $ 1 \le b_i \le m $ ) — the indices of safe columns.
输出格式
Print the minimum number of moves required to collect all the treasures.
输入输出样例
输入样例 #1
3 3 3 2
1 1
2 1
3 1
2 3
输出样例 #1
6
输入样例 #2
3 5 3 2
1 2
2 3
3 1
1 5
输出样例 #2
8
输入样例 #3
3 6 3 2
1 6
2 2
3 4
1 6
输出样例 #3
15