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

```
This entry was posted in poj. Bookmark the permalink.