P14004 [eJOI 2025] Vacation

Anton 和他的朋友们计划一起去度假。地点已经选好，但具体日期很难统一。 共有 $N$ 位朋友，每人事先提交了自己计划请假的日期。第 $i$ 位朋友原本安排的请假区间为从第 $L_i$ 天到第 $R_i$ 天（含两端）。为了最大化大家在一起的时间，每位朋友可以将自己的请假区间整体向前或向后平移：具体地，第 $i$ 位朋友可以选择一个整数 $d_i$，把他的请假区间移动为 $[L_i + d_i,\, R_i + d_i]$。其中，$d_i > 0$ 表示比原计划更晚请假，$d_i < 0$ 表示更早请假，$d_i = 0$ 表示保持原计划不变。 朋友们也意识到领导不会喜欢他们频繁调整，因此他们只会在**总位移**不超过某个整数 $K$ 的前提下移动自己的请假区间。形式化地，他们必须满足 $$ |d_0| + |d_1| + \cdots + |d_{N-1}| \le K. $$ 请帮助他们在最优调整的情况下，计算所有人**能够共同在一起**的天数的最大值。 ### 实现细节 你需要实现函数 `plan_vacation`： ```cpp int plan_vacation(int N, std::vector L, std::vector R, long long K) ``` - $N$：朋友人数； - $L$：长度为 $N$ 的正整数向量，第 $i$ 个数表示该朋友原计划请假的第一天； - $R$：长度为 $N$ 的正整数向量，第 $i$ 个数表示该朋友原计划请假的最后一天； - $K$：允许的总位移上限，即 $|d_0| + |d_1| + \cdots + |d_{N-1}|$ 的最大值。 该函数在每个测试中调用一次。它需要返回所有朋友能共同在一起的最大天数；如果完全无法做到让所有人同日有空，则返回 $0$。

输入格式如下： - 第 1 行：两个整数——$N$ 与 $K$； - 第 $2$ 到第 $N+1$ 行：每行两个整数——$L_i$ 与 $R_i$。

输出格式如下： - 第 1 行：一个整数——函数的返回值。

### 示例 考虑如下调用： ``` plan_vacation(3, {1, 5, 2}, {3, 9, 5}, 3) ``` 三位朋友原计划的请假区间分别为 $[1, 3]$、$[5, 9]$、$[2, 5]$。因此，可以让朋友 $0$ 把区间整体后移 $2$ 天、朋友 $1$ 把区间整体前移 $1$ 天，从而得到 $[3, 5]$、$[4, 8]$、$[2, 5]$。此时三人于第 $4$ 天与第 $5$ 天均可同时在一起，共有 $2$ 天。可以证明在 $K = 3$ 的限制下无法做得更好，因此函数应返回 $2$。 ### 约束 - $1 \le N \le 500\,000$ - $1 \le L_i \le R_i \le 10^9$ - $0 \le K \le 10^{18}$ ### 子任务 | 子任务 | 分值 | 依赖子任务 | 附加约束 | | :--: | :--: | :--: | :--: | | 0 | 0 | - | 样例。 | | 1 | 7 | - | $K = 0$ | | 2 | 11 | 1 | $K \le 1$ | | 3 | 6 | - | $K = 10^{18}$ | | 4 | 13 | 0 | $N \le 10^4$, $L_i \le 10$, $R_i \le 10$ | | 5 | 18 | 0 | $N \le 10^3$ | | 6 | 29 | 0, 4, 5 | $N \le 10^5$ | | 7 | 16 | 0–6 | 无附加约束。 | 翻译由 ChatGPT-5 完成。