308383: CF1510H. Hard Optimization

Memory Limit:512 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Hard Optimization

题意翻译

直线上有 $n$ 个线段 $[L_i, R_i]$,保证两个线段要么一个包含另一个,要么不交。 对于每个线段,选择它的一个子段 $[l_i, r_i ]$($l_i<r_i$),使得所有线段的子段不相交(但是可以拥有相同的端点),且所有子段的长度之和最大。

题目描述

You are given a set of $ n $ segments on a line $ [L_i; R_i] $ . All $ 2n $ segment endpoints are pairwise distinct integers. The set is laminar — any two segments are either disjoint or one of them contains the other. Choose a non-empty subsegment $ [l_i, r_i] $ with integer endpoints in each segment ( $ L_i \le l_i < r_i \le R_i $ ) in such a way that no two subsegments intersect (they are allowed to have common endpoints though) and the sum of their lengths ( $ \sum_{i=1}^n r_i - l_i $ ) is maximized.

输入输出格式

输入格式


The first line contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^3 $ ) — the number of segments. The $ i $ -th of the next $ n $ lines contains two integers $ L_i $ and $ R_i $ ( $ 0 \le L_i < R_i \le 10^9 $ ) — the endpoints of the $ i $ -th segment. All the given $ 2n $ segment endpoints are distinct. The set of segments is laminar.

输出格式


On the first line, output the maximum possible sum of subsegment lengths. On the $ i $ -th of the next $ n $ lines, output two integers $ l_i $ and $ r_i $ ( $ L_i \le l_i < r_i \le R_i $ ), denoting the chosen subsegment of the $ i $ -th segment.

输入输出样例

输入样例 #1

4
1 10
2 3
5 9
6 7

输出样例 #1

7
3 6
2 3
7 9
6 7

说明

The example input and the example output are illustrated below. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1510H/5f16544f7c2f9028951dcbf751c8ac0ade7eabbf.png)![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1510H/542e72d4ef7e3e36f2e2986d0a2d511f77dc8445.png)

Input

题意翻译

直线上有 $n$ 个线段 $[L_i, R_i]$,保证两个线段要么一个包含另一个,要么不交。 对于每个线段,选择它的一个子段 $[l_i, r_i ]$($l_i<r_i$),使得所有线段的子段不相交(但是可以拥有相同的端点),且所有子段的长度之和最大。

加入题单

上一题 下一题 算法标签: