展览会(exhibition)
题目描述
有一场展览会,一共有 $n$ 个展馆,每一个展馆有一个开放时间 $l_i\sim r_i$,注意,每一个展馆在第 $l_i$ 时刻开启,在第 $r_i$ 时刻关闭(即:包含 $l_i$ 但不包含 $r_i$)。
两两展馆之间都有道路,并且只有在两个展馆同时开放时道路才会开放。
道路每开放 $1$ 个单位的时间就需要消耗 $1$ 个单位的费用,现在主办方想要保留若干条道路,希望所有道路开放的总时间最小,并且要求所有保留的道路开放时间不能为零且所有的展馆能够被道路连通,问最小的每一条保留道路开放的时间总和是多少。
输入格式
从 exhibition.in
中读入数据。
输入一共 $n+1$ 行。
第一行一个正整数 $n$ 。
第 $2\sim n+1$ 行每行有两个数 $l_i,r_i$ 。
输出格式
输出到 exhibition.out
中。
一行一个数,最小开放的总时间。
如果展馆无法通过开放时间不为 $0$ 的道路连通,输出 -1
。
输入样例 1
3
1 4
2 6
3 4
输出样例 1
2
输入样例 2
2
1 3
3 5
输出样例 2
-1
输入输出样例 3
见下发文件中的 ex_exhibition.in/out
数据规模
对于 $100\%$ 的数据,保证: $1\leq n\leq 10^5$,$1\leq l_i
子任务如下表所示:
子任务编号 | $n$ | 特殊性质 | 分值 |
---|---|---|---|
1 | - | 保证数据无解 | 1 |
2 | $\leq 1000$ | - | 10 |
3 | - | $1\leq l | 5 |
4 | $\leq 1\times 10^4$ | - | 30 |
5 | $\leq 5\times 10^4$ | - | 20 |
6 | - | A | 10 |
7 | - | - | 24 |
特殊性质 A : 保证不存在一个展馆在另一个展馆 $j$ 开展之后开展,并且在 $j$ 结束展览之前结束。即:$\nexists i$ 使得 $\exists j\neq i,l_j\leq l_i < r_i \leq r_j$ 。