Bassline

Luogu
IDLGP8551
Time1000ms
Memory128MB
DifficultyP3
洛谷原创O2优化洛谷月赛
本题中,区间 $[l,r]$ 指所有大于等于 $l$ 且小于等于 $r$ 的整数组成的集合,如 $[3,3]$ 代表 $\{3\}$,$[3,7]$ 代表 $\{3,4,5,6,7\}$。 给定 $n$ 个区间,第 $i$ 个区间是 $[l_i,r_i]$。 你需要选择两个整数 $x\le y$,满足: - 对于所有区间 $[l_i,r_i]$($1\le i \le n$),以下两个条件之一满足: 1. $[x,y]$ 被 $[l_i,r_i]$ 包含,换言之, $[x,y]\cap[l_i,r_i]=[x,y]$。 2. $[x,y]$ 与 $[l_i,r_i]$ 无交集,换言之,$[x,y]\cap[l_i,r_i]=\varnothing$。 若有 $k$ 个区间满足条件 1,则你的得分是 $k(y-x)$。输出你最大的可能的得分。 ## Input 第一行一个正整数表示 $n$。 接下来 $n$ 行,每行两个数 $l_i,r_i$,描述一个区间。 ## Output 一行一个自然数表示答案。 [samples] ## Background fuwa↑ fuwa↑ fuwa↑ fuwa↑ 赫尔德开始使用当下热潮的聊天软件 BassLine,那么第一步自然是加好友了!加好友既需要确认自己和对方有共同兴趣,又需要能加到足够多的好友。赫尔德将其抽象成了下面这个问题,让你来帮她解决。 ## Note **【样例解释】** 对于样例,$[5,6]$ 是最优的区间之一,其含于 $[4,7],[5,9]$,且与 $[1,3],[7,10]$ 没有交集。此时 $k=2$,因此答案为 $2\times(6-5)=2$。$[1,3]$ 也是一个最优的区间。 $[5,7]$ 并非合法的区间,因为它与 $[7,10]$ 有交集,也并不含于 $[7,10]$。 --- **【数据范围】** 对于所有数据保证 $1 \le n \le 3 \times {10}^5$,$1 \le l_i \le r_i \le 3 \times {10}^5$。 - 子任务 1(20 分):$n,l_i,r_i \le 10$; - 子任务 2(20 分):$n \le {10}^3$; - 子任务 3(20 分):$l_i, r_i \le {10}^3$; - 子任务 4(40 分):无特殊限制。
Samples
Input #1
4
1 3
4 7
5 9
7 10
Output #1
2
API Response (JSON)
{
  "problem": {
    "name": "Bassline",
    "description": {
      "content": "本题中,区间 $[l,r]$ 指所有大于等于 $l$ 且小于等于 $r$ 的整数组成的集合,如 $[3,3]$ 代表 $\\{3\\}$,$[3,7]$ 代表 $\\{3,4,5,6,7\\}$。 给定 $n$ 个区间,第 $i$ 个区间是 $[l_i,r_i]$。 你需要选择两个整数 $x\\le y$,满足: - 对于所有区间 $[l_i,r_i]$($1\\le i \\le n$),以下两个条件之",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8551"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "本题中,区间 $[l,r]$ 指所有大于等于 $l$ 且小于等于 $r$ 的整数组成的集合,如 $[3,3]$ 代表 $\\{3\\}$,$[3,7]$ 代表 $\\{3,4,5,6,7\\}$。\n\n给定 $n$ 个区间,第 $i$ 个区间是 $[l_i,r_i]$。\n\n你需要选择两个整数 $x\\le y$,满足:\n\n- 对于所有区间 $[l_i,r_i]$($1\\le i \\le n$),以下两个条件之...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments