JOI春合宿2008Day2 cheating

適当ににぶたんすると通る
問題文読み間違って無駄に難しくしてた...

#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;

int n, m;
int x[100000], y[100000];

bool C(int k){
    int crt = -INT_MAX, num = 0;
    for(int i = 0; i < m && num <= n; i++){
	if(crt + k < x[i]){
	    num++;
	    crt = x[i];
	}
    }
    if(num > n) return false;
    crt = -INT_MAX;
    for(int i = 0; i < m && num <= n; i++){
	if(crt + k < y[i]){
	    num++;
	    crt = y[i];
	}
    }
    if(num > n) return false;
    return true;
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++) scanf("%d %d", &x[i], &y[i]);
    sort(x, x + m);
    sort(y, y + m);
    int lb = -1, ub = INT_MAX;
    while(ub > lb + 1){
	int mid = (lb + ub) / 2;
	if(C(mid)) ub = mid;
	else lb = mid;
    }
    printf("%d\n", ub);
    return 0;
}