4009: Doges

时间限制: 1 Sec  内存限制: 256 MB

提交: 39  解决: 8

[][][]

题目描述

在一个遥远的地方，住着n只 Doge，它们分别被编号为1到n之间的正整数。

有一天，一个叫 Jrisme 的人来到这里，进行了一些「虐狗」行为。具体的，Jrisme 每次会虐编号连续的一些 Doge。现给出每次虐狗的区间，求最幸运（被虐次数最多）Doge 被虐了多少次。

输入

第一行两个正整数n和m，分别表示 Doge 的数量和 Jrisme 的虐狗次数。

从第二行开始，之后的m 行，第i行为两个正整数 li、ri，表示 Jrisme 虐了编号在区间 [li,ri]内的 Doge。

输出

一行一个整数，最幸运的 Doge 的被虐次数。

样例输入

10 31 44 74 9

样例输出

3

提示

对于 100%的数据，1≤n≤10⁹，1≤m≤200000，1≤li≤ri≤n。

来源

1 #include
      
        2 #include
       
         3 #include 
        
          4 using namespace std; 5 int  n,m; 6  7 struct node 8 { 9     int TT,wi;10 }a[400000+10];11 int cmp(struct node x,struct node y)12 {13     if(x.TT==y.TT)14         return x.wi>y.wi;15     return x.TT