问题 H: 堆砖游戏(stacking)

问题 H: 堆砖游戏(stacking)

时间限制: 1 Sec  内存限制: 128 MB
提交: 15  解决: 6
[提交] [状态] [讨论版] [命题人:]

题目描述

一开始给定 N(1 ≤ N ≤ 1000000, N 为奇数)个单位的空地,分别以 1..N
表示。再给出一个有 K 个指令的序列(1 ≤ K ≤ 25000),每个指令格式为“A B”,
意味着在 A..B 的区域各增加一块砖。例如,如果给定区域为“10 13”,那么将在
区域 10,11,12,13 的位置各增加一个砖块。
请编程求出完成所有工作后,这 N 个区域按砖数排序后排在中间位置的区域
的砖的数目,即求砖数的中位数(由于 N 为奇数,所以这个值是唯一的)。

输入

第一行两个整数 N 和 K,之间用一个空格隔开;
第 2 到 1+K 行,每行两个整数 A 和 B 表示放砖的指令,之间用一个空格隔开。
1 ≤ A ≤ B ≤ N。

输出

输出一行一个整数,表示完成所有工作后,这 N 个区域按砖数排序后排在中
间位置的区域的砖的数目。

样例输入

7 4 
5 5 
2 4 
4 6
3 5

样例输出

1

提示

数据规模:
对于 70%的数据满足:N, K ≤ 10000;
对于 100%的数据满足:N ≤ 1000000, K ≤ 25000。

[提交][状态]