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

AT_abc256_d.[ABC256D] Union of Interval

普及-

通过率：0%

AC君温馨提醒

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

题目描述

对于实数 L,RL,R，由所有满足 L≤x<RL \leq x < R 的实数组成的集合记作 [L,R)[L,R)。这种形式表示的集合称为右半开区间。

给定 NN 个右半开区间 [Li,Ri)[L_i, R_i)。它们的并集记作 SS。请用最少数量的右半开区间的并集来表示 SS。

输入格式

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

NN
L1L_1 R1R_1
⋮\vdots
LNL_N RNR_N

输出格式

假设 SS 可以用最少 kk 个右半开区间的并集表示。请按 XiX_i 升序输出这 kk 个右半开区间 [Xi,Yi)[X_i, Y_i)，每行一个区间：

X1X_1 Y1Y_1
⋮\vdots
XkX_k YkY_k

输入输出样例

  • 输入#1

    3
10 20
20 30
40 50

    输出#1

    10 30
40 50

  • 输入#2

    3
10 40
30 60
20 50

    输出#2

    10 60

说明/提示

限制条件

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

样例解释 1

33 个右半开区间 [10,20),[20,30),[40,50)[10,20),[20,30),[40,50) 的并集等价于 22 个右半开区间 [10,30),[40,50)[10,30),[40,50) 的并集。

样例解释 2

33 个右半开区间 [10,40),[30,60),[20,50)[10,40),[30,60),[20,50) 的并集等价于 11 个右半开区间 [10,60)[10,60)。

由 ChatGPT 4.1 翻译

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

首页