AT_agc040_b.[AGC040B] Two Contests

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一场有 $10^9$ 名编号从 $1$ 到 $10^9$ 的参赛者参加的大会。在这场大会中，将举办 $2$ 场竞赛。

作为竞赛的题目，准备了 $N$ 道编号从 $1$ 到 $N$ 的题目。对于第 $i$ 道题，如果被出题，则编号在 $L_i$ 到 $R_i$ 之间的所有参赛者都能答对，除此之外的参赛者都无法解答。

这些 $N$ 道题目需要分配到 $2$ 场竞赛中，每道题必须且只能在一场竞赛中被出题。同时，每场竞赛都必须至少有一道题目。

每场竞赛的“乐趣”定义为能解答该场所有题目的参赛者人数。请你求出两场竞赛乐趣之和的最大可能值。

输入格式

输入以以下格式从标准输入读入。

$N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

输出格式

请输出两场竞赛乐趣之和的最大可能值。

输入输出样例

输入#1
```
4
4 7
1 4
5 8
2 5
```
输出#1
```
6
```
输入#2
```
4
1 20
2 19
3 18
4 17
```
输出#2
```
34
```

输入#3

10
457835016 996058008
456475528 529149798
455108441 512701454
455817105 523506955
457368248 814532746
455073228 459494089
456651538 774276744
457667152 974637457
457293701 800549465
456580262 636471526

输出#3

540049931

说明/提示

限制条件

$2 \leq N \leq 10^5$
$1 \leq L_i \leq R_i \leq 10^9$
输入的所有值均为整数。

样例解释 1

最优的分配方式如下：

在第 $1$ 场竞赛中出题 $1,3$ 。编号为 $5,6,7$ 的参赛者能解答该场所有题目，因此该场竞赛的乐趣为 $3$ 。
在第 $2$ 场竞赛中出题 $2,4$ 。编号为 $2,3,4$ 的参赛者能解答该场所有题目，因此该场竞赛的乐趣为 $3$ 。
两场竞赛的乐趣之和为 $6$ 。无法使乐趣之和超过 $6$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页