题目详情题解（0）讨论（0）提交记录（0）

AT_past202212_l.区間

通过率：0%

AC君温馨提醒

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

题目描述

给定 NN 个数轴上的区间 [L1,R1],[L2,R2],…,[LN,RN][L_1, R_1], [L_2, R_2], \ldots, [L_N, R_N]。

集合 {1,2,…,N}\{1, 2, \ldots, N\} 的一个子集 SS 被称为“好集合”，当且仅当对于任意 i,j∈Si, j \in S，必有以下两个条件之一成立：

  • 区间 [Li,Ri][L_i, R_i] 包含区间 [Lj,Rj][L_j, R_j]；
  • 区间 [Lj,Rj][L_j, R_j] 包含区间 [Li,Ri][L_i, R_i]。

这里，一个区间 [L,R][L, R] 包含另一个区间 [L′,R′][L', R'] 当且仅当 L≤L′L \leq L' 且 R′≤RR' \leq R。

请你求出好集合的最大可能大小。

输入格式

输入按如下格式从标准输入读入：

N L1 R1 L2 R2 ⋮ LN RNN\ L_1\ R_1\ L_2\ R_2\ \vdots\ L_N\ R_N

输出格式

请输出答案。

输入输出样例

  • 输入#1

    4
1 3
2 4
3 4
1 4

    输出#1

    3

  • 输入#2

    3
0 1
0 1
0 1

    输出#2

    3

  • 输入#3

    9
1 6
1 3
3 6
4 6
2 5
1 2
3 4
3 5
2 7

    输出#3

    4

说明/提示

样例解释 1

集合 {2,3,4}\{2, 3, 4\} 是一个最大化的好集合。事实上：

  • 对于 2,3∈S2, 3 \in S，[L2,R2][L_2, R_2] 包含 [L3,R3][L_3, R_3]；
  • 对于 2,4∈S2, 4 \in S，[L4,R4][L_4, R_4] 包含 [L2,R2][L_2, R_2]；
  • 对于 3,4∈S3, 4 \in S，[L4,R4][L_4, R_4] 包含 [L3,R3][L_3, R_3]；

因此答案应为 33。

数据范围

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 0≤Li<Ri≤1090 \leq L_i < R_i \leq 10^9
  • 输入中的所有值均为整数。

由 ChatGPT 5 翻译

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

首页