← 返回题目列表

AtCoder · tupc2024_q

Q. 使区间不相交

中文机器翻译题面 查看原题

配点 : 100 点

向环球杯参赛者

当包含在 Universal Cup 中时,此问题将被删除。因此,当使用 AtCoder 结果进行 Universal Cup 时,我们建议先解决其他问题。 给出了

問題文

N 给定了个半开区间。i 个半开区间的整数为 L_i,R_i 可以表示为 [L_i,R_i) 。

你可以进行以下操作任意次数( 0 次也可以)。

  • 2N 整数 给出了 L_1,R_1,L_2,R_2,\dots,L_N,R_N 出 1 选择其中一个,使其值 1 增加或 1 减少。

你的目标是,N 个半开区间 [L_1,R_1), [L_2,R_2),\dots,[L_N,R_N) 互不相交。 更严格地说,1\le i\lt j\le N 所有整数的组合 (i,j) 对于,『L_i\le x\lt R_i 和 L_j\le x\lt R_j 的实数 x 不存在』这样的情况。

但是, 运算前设定中包含的 L\ge R 时,半开区间 [L,R) 表示空集,空集与任意区间都不相交。

请找出为了达成目标所需的最少操作次数。

T 会给出

制約

  • 1 \le T \le 10^5
  • 2 \leq N \leq 2 \times 10^5
  • 1 \le L_i\lt R_i \le 10^9
  • 1 个测试用例,需要针对每个测试用例回答。 N 的总和是 2\times 10^5 以下
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个案例均按以下格式给出。 打印

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

出力

T 行。i 在线 i 输出第 N 个测试用例的答案。


入力例 1

4
3
1 4
3 7
6 7
2
1 1000000000
1 1000000000
2
1 2
2 3
4
20 25
3 22
3 23
3 24

出力例 1

2
999999999
0
43

1 对于第二个测试用例,例如

  • R_1 该值应乘以 1 减少
  • L_3 该值应乘以 1 增加

与操作之后,3 个区间变为 [1,3),[3,7),[7,7) ,它们彼此不相交。
2 由于可以证明少于次操作无法达成目标,1 个测试用例的答案 2 。