← 返回题目列表

AtCoder · abc014_3

C. At彩

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

問題文

 AtColor 是 直到0 到 1,000,000 到 1,000,001 我决定出售具有一定密度的灰色油漆。0 是最黑的,1,000,000 是最白的油漆。

 然而,人们发现,虽然密度存在令人难以置信的数量差异,但消费者无法分辨出更细微的差异。知道这一点后,AtColor 决定停止生产不受欢迎的密度的涂料,而是只销售最受欢迎的密度之一。

 为了实现上述目标,AtColor 决定进行一项调查,了解最受欢迎的涂料的销量。 当 AtColor 对消费者进行一项调查,询问他们想要购买哪个范围的油漆密度时,他们发现 满足a ≦ x ≦ b 的密度 x 涂料以“购买”的形式提供。 获得 n 结果。

 您的工作是创建一个程序,使用此信息输出购买最多消费者购买的油漆颜色的消费者数量。


入力

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

n
a_{1}\ b_{1}
a_{2}\ b_{2}
:
a_{n}\ b_{n}
  • 1 行显示问卷信息的数量。 给出了 n (1 ≦ n ≦ 100,000) 。
  • 继续 2 从行 n行代表每个调查问卷信息。 a_i,b_i(0≦a_i≦b_i≦1,000,000) 分别是 代表第 i 条问卷信息密度下限和上限(包括边缘)的整数,以空格分隔。

部分点

这个问题有两个数据集,并且为每个数据集设置了部分点。 如果您对满足

  • 1≦n≦2,000 的数据集 1 的回答正确 给出 30 点。
  • 如果您在没有附加约束的情况下在数据集 2 中回答正确, 70 点。

出力

对于最多消费者购买的颜色,计算购买该颜色的消费者数量。 在 1 行输出。在输出末尾插入换行符。


入力例1

4
0 2
2 3
2 4
5 6

出力例1

3
  • 密度 0,1,4,5,6 涂料可由一名消费者购买。
  • 密度 2 油漆由三位消费者购买。
  • 密度 3 油漆可由两名消费者购买。
  • 没有人会购买其他密度的油漆。

因此, 输出3 。


入力例2

4
1000000 1000000
1000000 1000000
0 1000000
1 1000000

出力例2

4