paranoid.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 82 行

{
PROG:paranoid
LANG:PASCAL
}

program paranoid;
const
  maxn=100000;
type
  interval=record
    start,finish,order:longint;
  end;
var
  fin,fout:text;
  int:array[1..maxn]of interval;
  n,l,r,try,i:longint;
procedure qsort(s,t:longint);
  var
    i,j,ran:longint;
    p:interval;
  begin
    if s>=t then exit;
    ran:=s+random(t-s+1);
    p:=int[ran];
    int[ran]:=int[s];
    i:=s;j:=t;
    repeat
      while (i<j) and (int[j].finish>=p.finish) do dec(j);
      if i=j then break;
      int[i]:=int[j];inc(i);
      while (i<j) and (int[i].finish<=p.finish) do inc(i);
      if i=j then break;
      int[j]:=int[i];dec(j);
    until i=j;
    int[i]:=p;
    qsort(s,i-1);
    qsort(i+1,t);
  end;
function ok(x:longint):boolean;
  var
    now,i:longint;
  begin
    now:=-1;
    for i:=1 to n do
      if int[i].order<=x then
        if int[i].start>now then
          now:=int[i].start
        else begin
          ok:=false;
          exit;
        end;
    ok:=true;
  end;
begin
  assign(fin,'paranoid.in');
  reset(fin);
  readln(fin,n);
  for i:=1 to n do begin
    readln(fin,int[i].start,int[i].finish);
    int[i].order:=i;
  end;
  close(fin);

  qsort(1,n);

  l:=1;r:=n;
  repeat
    try:=(l+r) div 2;
    if ok(try) then begin
      if try=n then break;
      if ok(try+1) then l:=try+1 else break;
    end
    else
      r:=try-1;
  until false;

  assign(fout,'paranoid.out');
  rewrite(fout);
  writeln(fout,try);
  close(fout);
end.