配点 : 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 。