POJ 3179 Corral the Cows——線分樹+離散化

アルゴリズムの検討:
まずy座標に従って順番を並べます.2分の1の答えは,線分木を用いて実行可能か否かを判断する.
これは離散化ではないでしょうか.広義の離散化だろう.
最初は更新していませんでしたが、エラーを意識して更新を加えたのが逆に間違っていたので、怠惰に線分樹buildを盗んでlog 10000回、時間の複雑さが(log 10000)^2*10000になり、葛藤してしまいました・・・
実はbuildほど線分木を何度も使わないのです.
コード:

program corral;//By_Thispoet

const

	maxn=505;maxx=10005;

var

	i,j,p,c,n,mid,left,right,ans,k	:longint;

	tree							:array[0..maxx*10]of record l,r,num:longint;end;

	x,y								:array[0..maxn]of longint;



procedure swap(var i,j:longint);

begin

	if i<>j then begin i:=i xor j;j:=i xor j;i:=i xor j;end;

end;



procedure qsort(l,r:longint);

var i,j,k:longint;

begin

	i:=l;j:=r;k:=y[i+random(j-i+1)];

	repeat

		while y[i]<k do inc(i);while y[j]>k do dec(j);

		if i<=j then begin

			swap(x[i],x[j]);swap(y[i],y[j]);inc(i);dec(j);

		end;

	until i>j;

	if l<j then qsort(l,j);if i<r then qsort(i,r);

end;



procedure build_tree(code,l,r:longint);

var mid:longint;

begin

	tree[code].l:=l;tree[code].r:=r;tree[code].num:=0;

	if l+1>=r then exit;mid:=(l+r)>>1;

	build_tree(code*2,l,mid);build_tree(code*2+1,mid,r);

end;



procedure insert_tree(code,l,r,data:longint);

var mid:longint;

begin

	if (tree[code].l=l)and(tree[code].r=r) then begin

		inc(tree[code].num,data);exit;

	end;mid:=(tree[code].l+tree[code].r)>>1;

	if mid>=r then insert_tree(code*2,l,r,data) else insert_tree(code*2+1,l,r,data);

	tree[code].num:=tree[code*2].num+tree[code*2+1].num;

end;



function count(code,l,r:longint):longint;

var mid:longint;

begin

	if (tree[code].l=l)and(tree[code].r=r) then exit(tree[code].num);

	mid:=(tree[code].l+tree[code].r)>>1;

	if mid>=r then exit(count(code*2,l,r)) else if mid<=l then exit(count(code*2+1,l,r));

	exit(count(code*2,l,mid)+count(code*2+1,mid,r));

end;



function min(i,j:longint):longint;

begin

	if i<j then exit(i);exit(j);

end;



function check(pos:longint):boolean;

begin

	if pos=0 then exit(false);p:=0;

	for i:=1 to n do begin

		while (p<n)and (y[p+1]-y[i]<pos) do begin

			inc(p);insert_tree(1,x[p]-1,x[p],1);

		end;

		if p-i+1>=c then begin

			for j:=i to p do if count(1,x[j]-1,min(x[j]+pos-1,maxx))>=c then exit(true);

		end;

		insert_tree(1,x[i]-1,x[i],-1);

	end;

	exit(false);

end;



begin

	readln(c,n);randomize;

	for i:=1 to n do readln(x[i],y[i]);qsort(1,n);p:=0;

	left:=0;right:=maxx;

	while left<=right do begin

		mid:=(left+right)>>1;

		build_tree(1,0,maxx);

		if check(mid) then begin

			right:=mid-1;ans:=mid;

		end else left:=mid+1;

	end;

	writeln(ans);

end.