比赛 NOIP2008集训模拟4 评测结果 AWAAWAAWAA
题目名称 彩色穿孔卡片 最终得分 70
用户昵称 lc 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2008-11-13 11:01:20
显示代码纯文本
program punch;
 type
   treetype=^node;
   node=record
       b:boolean;
       left,right:treetype;
     end;
 var
     ok:boolean;
     ans,max,i,n:longint;
     l,r:array[1..10000] of longint;
     tree:treetype;

procedure init;
 var
     i:longint;
 begin
  readln(n);
  max:=0;
  for i:=1 to n do
    begin
     read(l[i],r[i]);
     if r[i]>max then max:=r[i];
    end;
 end;

procedure Insert(var tree:treetype; le,ri:longint);
 var
    mid:longint;

 begin
  if tree=nil
     then begin
            new(tree);
            tree^.left:=nil; tree^.right:=nil;
            tree^.b:=false
          end;
  if tree^.b then exit;
  if r[i]<=le then exit;
  if l[i]>=ri then exit;
  if (l[i]<=le) and (r[i]>=ri)
  then begin
         if tree^.b=false
         then begin
              tree^.b:=true;
              ok:=true;
              end;
        exit
       end;
  mid:=(le+ri) div 2;
  Insert(tree^.left,le,mid);
  Insert(tree^.right,mid,ri);

 end;


begin
 assign(input,'punch.in');
 assign(output,'punch.out');
 reset(input); rewrite(output);
 init;
  for i:=n downto 1 do
    begin
    ok:=false;
    Insert(tree,0,max);
    if ok then inc(ans);
    end;
writeln(ans);
close(input); close(output);
end.