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;
}