[CCO 2022] Double Attendance

Luogu

IDLGP10052

Time3000ms

Memory1024MB

DifficultyP6

2022CCO（加拿大）

由于你的学校课程安排过于抽象，你的两门课程将在两个不同的教室里同时开始！你一次只能在一个地方，所以你只能在两个教室之间来回溜达，希望能够抓住两门课程的重点。两个教室的编号分别是 $1$ 和 $2$。在教室 $i$，老师将在课堂上展示 $N_{i}$ 张不同的幻灯片，第 j 张幻灯片将在时间区间 $\left(A_{i, j}, B_{i, j}\right)\left(0 \leq A_{i, j}<B_{i, j}\right)$ 内展示，其中 $A_{i, j}$ 和 $B_{i, j}$ 是从课堂开始后以秒为单位计算的时间。在两个教室里，不会在某个时间点同时展示多张幻灯片。例如，一个课堂可能在 $(1,2)$ 和 $(5,6)$ 这两对时间区间内有幻灯片展示，或者在 $(10,20)$ 和 $(20,30)$ 这两对时间区间内有幻灯片展示，但不会在 $(10,20)$ 和 $(19,30)$ 这两对时间区间有幻灯片展示。你在教室 $1$ 开始一天的课程，两门课程都在时刻 $0$ 开始。在那之后，你可以在任何时间点（不一定是整数秒）花费 $K$ 秒从你当前的教室移动到另一个教室。如果你在展示幻灯片的时间区间内在其教室里花费了正数时间，你就认为自己看到了这张幻灯片。当你在两个教室之间移动的 $K$ 秒内，你不在任何一个教室里，因此无法看到任何幻灯片。例如，如果教室 $1$ 在时间区间 $(10,20)$ 展示一张幻灯片，教室 $2$ 在时间区间 $(15,25)$ 展示一张幻灯片，而 $K=8$，那么如果你在时间 $11.5$ 秒时从教室 $1$ 移动到教室 $2$（到达时间为 $19.5$ 秒），你就能看到两张幻灯片。另一方面，如果你在时间 $17$ 秒时离开教室 $1$（到达时间为 $25$ 秒），那么你将在教室 $2$ 的幻灯片停止展示后才进入教室，因此你会错过它。你想要知道你能看到的不同幻灯片的最大数量是多少。 ## Input 第一行包含三个用空格分隔的整数，$N_{1}, N_{2}$ 和 $K$。接下来的 $N_{1}$ 行，每行包含两个用空格分隔的整数 $A_{1, i}$ 和 $B_{1, i}\left(1 \leq i \leq N_{1}\right)$。接下来的 $N_{2}$ 行，每行包含两个用空格分隔的整数，$A_{2, i}$ 和 $B_{2, i}\left(1 \leq i \leq N_{2}\right)$。 ## Output 输出一个整数，表示你能看到的不同幻灯片的最大数量。 [samples] ## Note ## 样例 1 解释一种可能的最优策略是在教室 $1$ 一直待到时间 $11.5$，然后移动到教室 $2$（到达时间为 $19.5$），一直待到时间 $19.6$，最后返回教室 $1$（到达时间为 $27.6$）。在这个过程中，你将看到除了第 $3$ 张幻灯片以外的所有幻灯片。你不可能看到所有的 $4$ 张幻灯片。 ## 样例 2 解释即使你在课程开始时立即移动到教室 $2$（例如，在时间 $0.0001$），你也会错过那里展示的前两张幻灯片。因此，你最多可以看到四张幻灯片。 ## 数据范围对于所有的数据，有 $1 \leq N_{i} \leq 3\times 10^5$，$0 \leq A_{i, j}<B_{i, j} \leq 10^{9}$，$1 \leq K \leq 10^{9}$。子任务编号|分值|$N_{i}$|$A_{i, j},B_{i, j}$ :-:|:-:|:-:|:-: $1$|$20$|$1 \leq N_{i} \leq 10$|$0 \leq A_{i, j}<B_{i, j} \leq 2000$ $2$|$40$|$1 \leq N_{i} \leq 2000$|$0 \leq A_{i, j}<B_{i, j} \leq 2000$ $3$|$24$|$1 \leq N_{i} \leq 2000$|$B_{i, j}-A_{i, j} \leq 2 K$ $4$|$16$|$1 \leq N_{i} \leq 3\times 10^5$|$0 \leq A_{i, j}<B_{i, j} \leq 10^{9}$

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[CCO 2022] Double Attendance",
    "description": {
      "content": "由于你的学校课程安排过于抽象，你的两门课程将在两个不同的教室里同时开始！你一次只能在一个地方，所以你只能在两个教室之间来回溜达，希望能够抓住两门课程的重点。 两个教室的编号分别是 $1$ 和 $2$。在教室 $i$，老师将在课堂上展示 $N_{i}$ 张不同的幻灯片，第 j 张幻灯片将在时间区间 $\\left(A_{i, j}, B_{i, j}\\right)\\left(0 \\leq A_{i,",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10052"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "由于你的学校课程安排过于抽象，你的两门课程将在两个不同的教室里同时开始！你一次只能在一个地方，所以你只能在两个教室之间来回溜达，希望能够抓住两门课程的重点。\n\n两个教室的编号分别是 $1$ 和 $2$。在教室 $i$，老师将在课堂上展示 $N_{i}$ 张不同的幻灯片，第 j 张幻灯片将在时间区间 $\\left(A_{i, j}, B_{i, j}\\right)\\left(0 \\leq A_{i,...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments