问题 27070 --【USACO2012JAN】叠干草{Bronze2}

27070: 【USACO2012JAN】叠干草{Bronze2}

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

题目描述

叠干草{stacking.pas/c/cpp}

   

(1 <= N <= 1,000,000, N为奇数)堆干草,按1..N编号,开始时每堆高度都是0FJ给出K (1 <= K <= 25,000)条指令,每条指令包含两个用空格隔开的整数,例如”10 13”,表示给10,11,12,13这四堆干草分别叠加一捆干草,即高度均增加1

FJ想知道,干草对完后,这N堆干草高度的中位数是多少。

输入

     第一行,两个正整数NK

    2..K+1行,每行两个整数A B (1 <= A <= B <= N),表示一条指令。

输出

    一个整数,表示中位数。

样例输入

7 4
5 5
2 4
4 6
3 5

样例输出

1

提示



【样例说明】




堆完后,高度分别是0,1,2,3,3,1,0。排序后为0,0,1,1,2,3,3,故中位数是1




来源

[提交][状态]