- 题目提供者 FarmerJohn2
- 评测方式 云端评测
- 标签 单调队列 线段树 队列 USACO 2013 高性能
- 难度 省选/NOI-
- 时空限制 1000ms / 128MB
Farmer John has decided to assemble a panoramic photo of a lineup of his N cows (1 <= N <= 200,000), which, as always, are conveniently numbered from 1..N. Accordingly, he snapped M (1 <= M <= 100,000) photos, each covering a contiguous range of cows: photo i contains cows a_i through b_i inclusive. The photos collectively may not necessarily cover every single cow.
After taking his photos, FJ notices a very interesting phenomenon: each photo he took contains exactly one cow with spots! FJ was aware that he had some number of spotted cows in his herd, but he had never actually counted them. Based on his photos, please determine the maximum possible number of spotted cows that could exist in his herd. Output -1 if there is no possible assignment of spots to cows consistent with FJ's photographic results.
农夫约翰决定给站在一条线上的N(1 <= N <= 200,000)头奶牛制作一张全家福照片，N头奶牛编号1到N。
于是约翰拍摄了M(1 <= M <= 100,000)张照片，每张照片都覆盖了连续一段奶牛：第i张照片中包含了编号a_i 到 b_i的奶牛。但是这些照片不一定把每一只奶牛都拍了进去。
* Line 1: Two integers N and M.
* Lines 2..M+1: Line i+1 contains a_i and b_i.输出格式：
* Line 1: The maximum possible number of spotted cows on FJ's farm, or -1 if there is no possible solution.
There are 5 cows and 3 photos. The first photo contains cows 1 through 4, etc.
From the last photo, we know that either cow 3 or cow 4 must be spotted. By choosing either of these, we satisfy the first two photos as well.