Poj Solution 3179

http://poj.org/problem?id=3179

#include <stdio.h>
#include <algorithm>
using namespace std;

int sum[1024][1024],s;

inline int lowbit(int a)
{
    return a&(a^(a-1));
}

void init( )
{
    int i,j;
    
    for(i=1;i<=s;i++)
    for(j=1;j<=s;j++)
        sum[i][j]=0;
}

void set( int x, int y )
{
    int j;
    
    x++,y++;

    while(x<=s)
    {
        for(j=y;j<=s;j+=lowbit(j))
        {
            sum[x][j]++;
        }
        x+=lowbit(x);
    }
}

int count(int x,int y)
{
    int ans=0,j;
    
    while(x>0)
    {
        for(j=y;j>0;j-=lowbit(j))
        {
            ans+=sum[x][j];
        }
        x-=lowbit(x);
    }

    return ans;
}


int query( int l, int b, int r, int t )
{

    l++,b++,r++,t++;

    return count(r,t)-count(r,b-1)-count(l-1,t)+count(l-1,b-1);
}

int f[1001];
int x[500], y[500];
int t[1001], n;

bool check( int len, int c ) {
    int i, j, ti, tj;

    if( len < 0 )
        return false;

    for( i=0; i<2*n; i++ )
        t[i] = std::upper_bound( f, f+2*n+1, f[i]+len ) - f - 1;

    ti = -1;
    for( i=0; i<2*n; i++ ) {
        if( t[i] == ti )
            continue;
        
        ti = t[i];

        if( query( i, 0, ti, 2*n-1 ) >= c ) {
            tj = -1;

            for( j=0; j<2*n; j++ ) {
                if( tj == t[j] )
                    continue;

                tj = t[j];

                if( query( i, j, ti, tj ) >= c )
                    return true;
            }
        }
    }
    return false;
}

int main( ) {
    int i, c, a, b, ans;

    scanf( "%d%d", &c, &n );

    for( i=0; i<n; i++ ) {
        scanf( "%d%d", x+i, y+i );
        f[i*2] = x[i];
        f[i*2+1] = y[i];
    }
    
    s = 2*n;

    std::sort( f, f+2*n );

    f[2*n] = 20000000;

    init( );

    for( i=0; i<n; i++ ) {
        a = std::lower_bound( f, f+2*n, x[i] ) - f;
        b = std::lower_bound( f, f+2*n, y[i] ) - f;
        set( a, b );
    }

    a = -1; b = f[2*n-1] - f[0];

    while( a < b-1 ) {
        ans = (a+b)/2;
        if( check( ans, c ) )
            b = ans;
        else
            a = ans;
    }

    printf( "%dn", b+1 );
    
    return 0;
}