lines

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 515 Accepted Submission(s): 241

Problem Description

John has several lines. The lines are covered on the X axis. Let A is a point which is covered by the most lines. John wants to know how many lines cover A.

Input

The first line contains a single integer

Output

For each case, output an integer means how many lines cover A.

Sample Input

1 2

2 2

2 4

3 4

5 1000

1 1

2 2

3 3

4 4

5 5

Sample Output

BC#20的1002题

区间的数据范围去到1e8

只要离散一下再用差分标记搞就可以了

#include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  #include 
                  
                   using namespace std;typedef long long LL;typedef pair
                   
                     pii;#define X first#define Y secondconst int N = 300010 ;const int inf = 1e9+7;int cnt[N] , tot ;struct node { int x , xx , id ;}e[N];bool cmp1( const node &a , const node &b ){ return a.x < b.x ; }bool cmp2( const node &a , const node &b ){ return a.id < b.id ; }void run() { memset( cnt , 0 , sizeof cnt ) ; int n ; tot = 0 ; scanf("%d",&n); for( int i = 0 ; i < 2 * n ; ++i ){ scanf("%d",&e[i].x); e[i].id = i ; } sort( e , e + 2 * n , cmp1 ); e[0].xx = 1 ; for( int i = 1 ; i < 2 * n ; ++i ){ e[i].xx = ( e[i].x == e[i-1].x ? e[i-1].xx : e[i-1].xx + 1 ); } sort( e, e + 2 * n , cmp2 ) ; for( int i = 0 ; i < 2 * n ; i += 2 ){ cnt[ e[i].xx ] ++; cnt[ e[i+1].xx + 1 ] --; } int ans = 0 , sum = 0 ; for( int i = 0 ; i <= 2 * n ; ++i ){ sum += cnt[i]; ans = max( ans , sum ) ; } printf("%d\n",ans);}int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); #endif // LOCAL ios::sync_with_stdio(false); int _ ; scanf("%d",&_); while( _-- ) run() ;}