Cod sursa(job #25493)

Utilizator pelaspateSorin Fagateanu pelaspate Data 4 martie 2007 12:44:10
Problema Ograzi Scor 50
Compilator fpc Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 3.14 kb
{$q-,r-,s-,d-,i-}
const maxn=100006;oo=1000*1000;zero=ord('0');maxarb=1 shl 21;
var t:Text;
   DX,DY,OX,OY,O,O2:Array[0..maxn]of longint;
   aux,coord,oi,d1,d2,sol,nn,n,m,w,h,i,j,k:longint;S:string;
   function min(a,b:longint):longint;begin if a>b then min:=b else min:=a;end;
   Procedure MergeSort(lo,hi:longint;var A,B:array of longint);
   var i,j,juma,lg:longint;
   begin
      if lo=hi then A[lo]:=lo else
      begin
         juma:=(lo+hi)div 2;mergesort(lo,juma,b,a);mergesort(juma+1,hi,b,a);
         i:=lo;j:=juma+1;
         for lg:=lo to hi do if(j>hi)or(i<=juma)and(Dx[B[i]]<=Dx[B[j]]) then
         begin A[lg]:=B[i];inc(i);end else begin A[lg]:=B[j];inc(j);end;
      end;
   end;
   Procedure Qsort(lo,hi:longint);
   var i,j,midx:longint;
   begin
      i:=lo;j:=hi;midx:=Ox[(i+j)div 2];
      repeat
         while Ox[i]<midx do inc(i);while Ox[j]>midx do dec(j);
         if i<=j then
         begin
            aux:=Ox[i];Ox[i]:=Ox[j];Ox[j]:=aux;
            aux:=Oy[i];Oy[i]:=Oy[j];Oy[j]:=aux;
            inc(i);dec(j);
         end;
      until i>j;if lo<j then qsort(lo,j);if i<hi then qsort(i,hi);
   end;
var Arb:array[0..maxarb]of boolean;
   Procedure Act(nod,lo,hi,i,j:longint;val:boolean);
   var juma:longint;
   begin
      if (i<=lo)and(hi<=j) then Arb[nod]:=val else
      begin
         juma:=(lo+hi)div 2;
         if i<=juma then act(nod*2,lo,juma,i,j,val);
         if juma<j then act(nod*2+1,juma+1,hi,i,j,val);
      end;
   end;
   function get(cine:longint):boolean;
   var nod,lo,hi,juma:longint;
   begin
      get:=false;nod:=1;lo:=0;hi:=oo;
      repeat
         if arb[nod] then begin get:=true;break;end;
         juma:=(lo+hi)div 2;
         if cine<=juma then begin nod:=nod shl 1;hi:=juma;end
         else begin nod:=(nod shl 1) or 1;lo:=juma+1;end;
      until lo=hi;if arb[nod] then get:=true;
   end;
{var t1:longint;t2:longint absolute $0:$046c;}
begin
{   t1:=t2;}
   assign(T,'ograzi.in');reset(T);readln(T,n,m,w,h);
   for i:=1 to N do
   begin
      readln(T,s);
      for j:=1 to length(s) do if s[j]<>' ' then Dx[i]:=Dx[i]*10+ord(s[j])-zero else break;
      for k:=j+1 to length(S) do Dy[i]:=Dy[i]*10+ord(s[k])-zero;
      Dx[i+n]:=Dx[i]+w;Dy[i+n]:=dy[i];
   end;nn:=n*2;MergeSort(1,nn,O,O2);O[nn+1]:=nn+1;Dx[nn+1]:=oo*10;
   for i:=1 to M do
   begin
      readln(T,s);
      for j:=1 to length(s) do if s[j]<>' ' then Ox[i]:=Ox[i]*10+ord(s[j])-zero else break;
      for k:=j+1 to length(S) do Oy[i]:=Oy[i]*10+ord(s[k])-zero;
   end;close(T);Qsort(1,m);Ox[m+1]:=oo*10;
   d1:=1;oi:=1;
   for d2:=2 to nn+1 do if Dx[O[d1]]<>dx[O[d2]] then
   begin
      coord:=Dx[O[d1]];
      while Ox[oi]<coord do begin if get(Oy[oi]) then inc(sol);inc(oi);end;
      i:=d1;
      while (i<d2)and (O[i]<=n) do
      begin act(1,0,oo,DY[O[i]],min(oo,Dy[O[i]]+H),true);inc(i);end;
      while Ox[oi]=coord do begin if get(Oy[oi]) then inc(sol);inc(oi);end;
      while (i<d2)and (O[i]>n) do
      begin act(1,0,oo,DY[O[i]],min(oo,Dy[O[i]]+H),false);inc(i);end;
      d1:=d2;
   end;
   assign(t,'ograzi.out');rewrite(T);writeln(t,sol);close(T);
{   writeln((t2-t1)/18.2:0:6);}
end.