#PU1526. USACO 2025 US Open Contest, Platinum — Problem 3. Package Pickup

    ID: 1680 传统题 4000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:open25来源:usaco.orgscoring:equal_test_cases堆

USACO 2025 US Open Contest, Platinum — Problem 3. Package Pickup

USACO 2025 US Open Contest, Platinum — Problem 3. Package Pickup

题目描述

Note: The time limit for this problem is 4s, 2x the default. Farmer John has distributed cows and packages in a weird pattern across the number line using the following process: Farmer John chooses a number MM (1≤M≤10181 \le M \le 10^{18}). Farmer John chooses NN (1≤N≤2⋅104)1 \le N \le 2 \cdot 10^4) intervals [Li,Ri][L_i, R_i] to distribute cows in (1≤Li≤Ri≤10181 \le L_i \le R_i \le 10^{18}). He then places cows at locations Li,Li+M,Li+2M,…,RiL_i, L_i + M, L_i + 2M, \ldots, R_i. It is guaranteed that Ri−LiR_i - L_i is a multiple of MM. Farmer John chooses PP (1≤P≤2⋅104)1 \le P \le 2 \cdot 10^4) intervals [Ai,Bi][A_i, B_i] to distribute packages in (1≤Ai≤Bi≤10181 \le A_i \le B_i \le 10^{18}). He then places packages at locations Ai,Ai+M,Ai+2M,…,BiA_i, A_i + M, A_i + 2M, \ldots, B_i. It is guaranteed that Bi−AiB_i - A_i is a multiple of MM. Once the cows and packages are distributed, Farmer John wants to see how long it takes the cows to pick up the packages. Every second, Farmer John can issue a command to a single cow to move one unit left or right of their current position with his handy walkie talkie. If a cow travels to the position where a package is located, they are able to pick it up. Farmer John wants to know the minimum time in seconds that it would take the cows to pick up every package.

输入格式

The first line contains MM, NN, and PP. The next NN lines each contain two integers LiL_i and RiR_i. The next PP lines each contain two integers AiA_i and BiB_i.

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

100 3 7
10 10
20 20
30 30
7 7
11 11
13 13
17 17
24 24
26 26
33 33
22
In the above test case, suppose the cows and packages are numbered from left to
right. Farmer John can follow this procedure to pick up the packages in 22
seconds:
Issue $3$ lefts to cow $1$ so that it picks up package $1$
Issue
$3$ rights to cow $3$ so that it picks up package $7$
Issue $4$ rights
to cow $2$ so that it picks up package $5$
Issue $10$ rights to cow $1$
so that it picks up packages $2$, $3$, and $4$
Issue $2$ rights to cow
$2$ so that it picks up package $6$

样例 2

2 1 1
1 5
2 6
3
There are three cows and three packages. Farmer John can issue one right to each
cow.