Package Pickup

题目描述

注意：本题时间限制为 4s，是默认时间限制的 2 倍。 农夫约翰用如下过程在数轴上以一种奇怪的方式分布奶牛和包裹： 农夫约翰选择一个数 $M$（$1 \le M \le 10^{18}$）。 农夫约翰选择 $N$（$1 \le N \le 2 \cdot 10^4$）个区间 $[L_i, R_i]$ 来分布奶牛（$1 \le L_i \le R_i \le 10^{18}$）。随后他在位置 $L_i, L_i + M, L_i + 2M, \ldots, R_i$ 放置奶牛。保证 $R_i - L_i$ 是 $M$ 的倍数。 农夫约翰选择 $P$（$1 \le P \le 2 \cdot 10^4$）个区间 $[A_i, B_i]$ 来分布包裹（$1 \le A_i \le B_i \le 10^{18}$）。随后他在位置 $A_i, A_i + M, A_i + 2M, \ldots, B_i$ 放置包裹。保证 $B_i - A_i$ 是 $M$ 的倍数。 当奶牛和包裹都分布完后，农夫约翰想知道奶牛捡起包裹需要多久。每一秒，农夫约翰可以通过对讲机向一头奶牛下达一条指令，使其从当前位置向左或向右移动 1 个单位。如果一头奶牛走到某个包裹所在的位置，它就能捡起该包裹。农夫约翰想知道让奶牛捡起所有包裹所需的最少时间（秒数）。

输入格式

第一行包含 $M$、$N$ 和 $P$。 接下来 $N$ 行，每行包含两个整数 $L_i$ 和 $R_i$。 接下来 $P$ 行，每行包含两个整数 $A_i$ 和 $B_i$。

输出格式

输出一个整数，表示在每秒只能对一头奶牛下达一条左右移动指令的条件下，奶牛捡起所有包裹所需的最少时间。

100 3 7
10 10
20 20
30 30
7 7
11 11
13 13
17 17
24 24
26 26
33 33

22

2 1 1
1 5
2 6

3

提示

在上面的测试用例中，假设奶牛和包裹从左到右编号。农夫约翰可以按如下步骤在 22 秒内捡起包裹： 对奶牛 $1$ 下达 $3$ 次向左移动，使其捡起包裹 $1$ 下达 对奶牛 $3$ 下达 $3$ 次向右移动，使其捡起包裹 $7$ 下达 $4$ 次向右移动 对奶牛 $2$ 下达 $4$ 次向右移动，使其捡起包裹 $5$ 对奶牛 $1$ 下达 $10$ 次向右移动 使其捡起包裹 $2$、$3$ 和 $4$ 对奶牛 对奶牛 $2$ 下达 $2$ 次向右移动，使其捡起包裹 $6$ 第二个样例中，有三头奶牛和三个包裹。农夫约翰可以对每头奶牛各下达一次向右移动指令。 计分（SCORING）： 输入 3-4：保证奶牛和包裹的总数量不超过 $2 \cdot 10^5$ 输入 5-10：保证 $N, P \le 500$。 输入 11-13：保证包裹区间与奶牛区间均不相交。 输入 14-20：无额外限制。 题目作者：Suhas Nagar 和 Benjamin Qi

标签: USACO|2025|Platinum

来源

USACO|2025|Platinum