POJ3179CorraltheCows——线段树+离散化

program corral;//By_Thispoet
constmaxn&＃61;505;maxx&＃61;10005;
vari,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);
beginif i<>j then begin i:&＃61;i xor j;j:&＃61;i xor j;i:&＃61;i xor j;end;
end;procedure qsort(l,r:longint);
var i,j,k:longint;
begini:&＃61;l;j:&＃61;r;k:&＃61;y[i&＃43;random(j-i&＃43;1)];repeatwhile y[i]k do dec(j);if i<&＃61;j then beginswap(x[i],x[j]);swap(y[i],y[j]);inc(i);dec(j);end;until i>j;if lend;procedure build_tree(code,l,r:longint);
var mid:longint;
begintree[code].l:&＃61;l;tree[code].r:&＃61;r;tree[code].num:&＃61;0;if l&＃43;1>&＃61;r then exit;mid:&＃61;(l&＃43;r)>>1;build_tree(code*2,l,mid);build_tree(code*2&＃43;1,mid,r);
end;procedure insert_tree(code,l,r,data:longint);
var mid:longint;
beginif (tree[code].l&＃61;l)and(tree[code].r&＃61;r) then begininc(tree[code].num,data);exit;end;mid:&＃61;(tree[code].l&＃43;tree[code].r)>>1;if mid>&＃61;r then insert_tree(code*2,l,r,data) else insert_tree(code*2&＃43;1,l,r,data);tree[code].num:&＃61;tree[code*2].num&＃43;tree[code*2&＃43;1].num;
end;function count(code,l,r:longint):longint;
var mid:longint;
beginif (tree[code].l&＃61;l)and(tree[code].r&＃61;r) then exit(tree[code].num);mid:&＃61;(tree[code].l&＃43;tree[code].r)>>1;if mid>&＃61;r then exit(count(code*2,l,r)) else if mid<&＃61;l then exit(count(code*2&＃43;1,l,r));exit(count(code*2,l,mid)&＃43;count(code*2&＃43;1,mid,r));
end;function min(i,j:longint):longint;
beginif iend;function check(pos:longint):boolean;
beginif pos&＃61;0 then exit(false);p:&＃61;0;for i:&＃61;1 to n do beginwhile (p&＃61;c then beginfor j:&＃61;i to p do if count(1,x[j]-1,min(x[j]&＃43;pos-1,maxx))>&＃61;c then exit(true);end;insert_tree(1,x[i]-1,x[i],-1);end;exit(false);
end;beginreadln(c,n);randomize;for i:&＃61;1 to n do readln(x[i],y[i]);qsort(1,n);p:&＃61;0;left:&＃61;0;right:&＃61;maxx;while left<&＃61;right do beginmid:&＃61;(left&＃43;right)>>1;build_tree(1,0,maxx);if check(mid) then beginright:&＃61;mid-1;ans:&＃61;mid;end else left:&＃61;mid&＃43;1;end;writeln(ans);
end.