소포 수거

*참고: 이 문제의 시간 제한은 4초로, 기본값의 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\)의 배수임이 보장된다.

소와 소포가 배치된 후, 농부 존은 소들이 소포를 모두 수거하는 데 얼마나 걸리는지 알고 싶어 한다. 매초, 농부 존은 편리한 무전기로 소 한 마리에게 현재 위치에서 왼쪽 또는 오른쪽으로 한 칸 이동하라는 명령을 내릴 수 있다. 소가 소포가 있는 위치로 이동하면 그 소포를 수거할 수 있다. 농부 존은 소들이 모든 소포를 수거하는 데 걸리는 최소 시간(초)을 알고 싶어 한다.

Problem credits: Suhas Nagar and Benjamin Qi

SCORING

• 입력 3-4: 소와 소포의 총 개수가 \(2 \cdot 10^5\)를 넘지 않음이 보장된다
• 입력 5-10: \(N, P \le 500\)임이 보장된다.
• 입력 11-13: 소포 또는 소의 어떤 구간도 서로 겹치지 않음이 보장된다.
• 입력 14-20: 추가 제약 없음.

Problem credits: Suhas Nagar and Benjamin Qi

첫째 줄에 \(M\), \(N\), \(P\)가 주어진다.

다음 \(N\)개의 줄에 각각 두 정수 \(L_i\)와 \(R_i\)가 주어진다.

다음 \(P\)개의 줄에 각각 두 정수 \(A_i\)와 \(B_i\)가 주어진다.

매초 소 한 마리에게 왼쪽/오른쪽 명령을 하나씩 내릴 수 있을 때, 소들이 모든 소포를 수거하는 데 걸리는 최소 시간을 나타내는 하나의 정수를 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2024-2025 > US Open > Platinum