#2745. Photo

Photo

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

FarmerJohn\red{Farmer John }决定为他的 N\red{N }头奶牛(1<=N<=200,000\red{1 <= N <= 200,000})组合一张全景照片,与往常一样,这些奶牛的编号从 1..N\red{1..N }开始很方便。

因此,他拍摄了 M(1<=M<=100,000)\red{M (1 <= M <= 100,000) }张照片,每张照片都覆盖了一系列连续的奶牛:照片 i\red{i }包含奶牛 ai\red{a_i }bi\red{b_i }。这些照片可 能不一定涵盖每一头奶牛。

拍完照片后,FJ\red{FJ }注意到一个很有趣的现象:他拍的每张照片中都正好有一头有斑点的奶牛!FJ\red{FJ }知道他的牛群中有一些斑点奶牛,但他从未真正数过它们。

根据他的照片,请确定他的牛群中可能存在的最大可能的斑点奶牛数量。如果没有可能将斑点分配给与 FJ\red{FJ }的摄影结果一致的奶牛,则输出 1\red{-1}

给你一个长度的数轴和一个时间段,每个点段里有一个点,问有多少

输入格式

1\red{1 }行:两个整数 N\red{N }M\red{M}

2..M+1\red{2..M+1 }行:第 i+1\red{i+1 }行包含 ai\red{a_i }bi\red{b_i}

输出格式

1\red{1 }行:FJ\red{FJ }农场中发现的奶牛的最大可能数量,如果没有可能的解决方案,则为 1\red{-1}

样例

输入样例

5 3
1 4
2 5
3 4

输出样例

1

提示

输入细节:

5\red{5 }头奶牛和 3\red{3 }张照片。第一张照片包含奶牛 1\red{1 }4\red{4 }等。

输出细节:

从最后一张照片中,我们知道必须发现奶牛 3\red{3 }或奶牛 4\red{4}。通过选择其中任何一个,我们也可以满足前两张照片。

周六集训队线性优化

未参加
状态
已结束
规则
IOI
题目
5
开始于
2023-4-15 15:00
结束于
2023-4-19 19:00
持续时间
100 小时
主持人
参赛人数
28