AT_abc360_f.[ABC360F] InterSections

省选/NOI-

通过率：0%

AC君温馨提醒

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

题目描述

给定 $N$ 个编号为 $1$ 到 $N$ 的区间。区间 $i$ 为 $[L_i, R_i]$ 。

当且仅当满足 $(l_a < l_b < r_a < r_b)$ 或 $(l_b < l_a < r_b < r_a)$ 时，称区间 $[l_a, r_a]$ 与区间 $[l_b, r_b]$ 相交。

定义 $f(l, r)$ 为满足 $1 \leq i \leq N$ 且区间 $[l, r]$ 与区间 $i$ 相交的 $i$ 的个数。

请在所有满足 $0 \leq l < r \leq 10^9$ 的整数对 $(l, r)$ 中，找到使 $f(l, r)$ 取得最大值的 $(l, r)$ ，并在这些对中选择 $l$ 最小的。如果仍有多个解，则选择 $r$ 最小的（由于 $0 \leq l < r$ ，答案是唯一的）。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

请输出答案对 $(l, r)$ ，格式如下：

$l$ $r$

输入输出样例

输入#1
```
5
1 7
3 9
7 18
10 14
15 20
```
输出#1
```
4 11
```

输入#2

11
856977192 996441446
298251737 935869360
396653206 658841528
710569907 929136831
325371222 425309117
379628374 697340458
835681913 939343451
140179224 887672320
375607390 611397526
93530028 581033295
249611310 775998537

输出#2

396653207 887672321

说明/提示

限制条件

$1 \leq N \leq 10^5$
$0 \leq L_i < R_i \leq 10^9$ （ $1 \leq i \leq N$ ）
输入均为整数

样例解释 1

$f(l, r)$ 的最大值为 $4$ ，且使 $f(l, r)=4$ 的 $(l, r)$ 中， $l$ 的最小值为 $4$ 。满足 $f(l, r)=4$ 且 $l=4$ 的 $(l, r)$ 有以下 $5$ 种：

$(l, r)=(4, 11)$
$(l, r)=(4, 12)$
$(l, r)=(4, 13)$
$(l, r)=(4, 16)$
$(l, r)=(4, 17)$

其中 $r$ 的最小值为 $11$ ，因此输出 $4$ 和 $11$ 。

由 ChatGPT 4.1 翻译

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

首页