Cod sursa(job #2880)

Utilizator wefgefAndrei Grigorean wefgef Data 19 decembrie 2006 18:46:43
Problema Zota & Chidil Scor 70
Compilator fpc Status done
Runda Arhiva de probleme Marime 4.88 kb
program zc;
const hash=539751;
type pnod=^nod;
     nod=record
       v1,v2:longint;
       next:pnod;
     end;
var f:text;
    vx,vy,ux,uy,tx,ty:array[0..1300001] of longint;
    vec:array[-540000..539750] of pnod;
    n,m,i,a,b,j,k,cont,x1,x2,y1,y2,poz1,poz2,nr:longint;
    ch:char;
    sum:longint;

procedure insert(a,b:longint);
var q:pnod;
    p:longint;
begin
  p:=((a mod hash)+(b mod hash)) mod hash;
  if vec[p]=nil then begin
    new(q);q^.next:=nil;
    q^.v1:=a;q^.v2:=b;
    vec[p]:=q;
  end else begin
    new(q);q^.next:=vec[p];
    q^.v1:=a;q^.v2:=b;
    vec[p]:=q;
  end;
end;

function valid(a,b:longint):boolean;
var p:pnod;
begin
  if (a=0) and (b=0) then begin valid:=false; exit; end;
  valid:=true;
  p:=vec[((a mod hash)+(b mod hash)) mod hash];
  while p<>nil do begin
    if (p^.v1=a) and (p^.v2=b) then begin
      valid:=false;
      exit;
    end;
    p:=p^.next;
  end;
end;

procedure intercl1(st,dr,m:longint);
var i,j,k:longint;
begin
  if (vx[m]<vx[m+1]) or ((vx[m]=vx[m+1]) and (vy[m]<vy[m+1])) then
    exit;
  i:=st;
  j:=m+1;
  k:=st-1;
  while (i<=m) and (j<=dr) do
  begin
    k:=k+1;
    if (vx[i]<vx[j]) or ((vx[i]=vx[j]) and (vy[i]<vy[j])) then
      begin
        tx[k]:=vx[i];
        ty[k]:=vy[i];
        i:=i+1;
      end
    else
      begin
        tx[k]:=vx[j];
        ty[k]:=vy[j];
        j:=j+1;
      end;
  end;
  while i<=m do
    begin
      k:=k+1;
      tx[k]:=vx[i];
      ty[k]:=vy[i];
      i:=i+1;
    end;
  while j<=dr do
    begin
      k:=k+1;
      tx[k]:=vx[j];
      ty[k]:=vy[j];
      j:=j+1;
    end;
  for i:=st to dr do begin
    vx[i]:=tx[i];
    vy[i]:=ty[i];
  end;
end;

procedure merge1(st,dr:longint);
var m:longint;
begin
  if st<dr then
    begin
      m:=(st+dr) div 2;
      merge1(st,m);
      merge1(m+1,dr);
      intercl1(st,dr,m);
    end;
end;

procedure intercl2(st,dr,m:longint);
var i,j,k:longint;
begin
  if (uy[m]<uy[m+1]) or ((uy[m]=uy[m+1]) and (ux[m]<ux[m+1])) then
    exit;
  i:=st;
  j:=m+1;
  k:=st-1;
  while (i<=m) and (j<=dr) do
  begin
    k:=k+1;
    if (uy[i]<uy[j]) or ((uy[i]=uy[j]) and (ux[i]<ux[j])) then
      begin
        tx[k]:=ux[i];
        ty[k]:=uy[i];
        i:=i+1;
      end
    else
      begin
        tx[k]:=ux[j];
        ty[k]:=uy[j];
        j:=j+1;
      end;
  end;
  while i<=m do
    begin
      k:=k+1;
      tx[k]:=ux[i];
      ty[k]:=uy[i];
      i:=i+1;
    end;
  while j<=dr do
    begin
      k:=k+1;
      tx[k]:=ux[j];
      ty[k]:=uy[j];
      j:=j+1;
    end;
  for i:=st to dr do begin
    ux[i]:=tx[i];
    uy[i]:=ty[i];
  end;
end;

procedure merge2(st,dr:longint);
var m:longint;
begin
  if st<dr then
    begin
      m:=(st+dr) div 2;
      merge2(st,m);
      merge2(m+1,dr);
      intercl2(st,dr,m);
    end;
end;

function cauta1(st,dr,x,y:longint):longint;
var m:longint;
begin
  while st<=dr do begin
    m:=(st+dr) div 2;
    if (vx[m]<x) or ((vx[m]=x) and (vy[m]<=y)) then begin
      if (vx[m+1]>x) or ((vx[m+1]=x) and (vy[m+1]>y)) or (m=cont)
        then begin cauta1:=m; exit; end
        else st:=m+1
    end else dr:=m-1;
  end;
  cauta1:=0;
end;

function cauta2(st,dr,x,y:longint):longint;
var m:longint;
begin
  while st<=dr do begin
    m:=(st+dr) div 2;
    if (uy[m]<y) or ((uy[m]=y) and (ux[m]<=x)) then begin
      if (uy[m+1]>y) or ((uy[m+1]=y) and (ux[m+1]>x)) or (m=cont)
        then begin cauta2:=m; exit; end
        else st:=m+1
    end else dr:=m-1;
  end;
  cauta2:=0;
end;

begin
  assign(f,'zc.in');reset(f);
    readln(f,n,m);
    for i:=1 to n do begin
      readln(f,a,b);
      for j:=a-2 to a+2 do
      for k:=b-2 to b+2 do
      if abs(j-a)+abs(k-b)<=2 then
      if valid(j,k) then begin
        insert(j,k);
        inc(cont);
        vx[cont]:=j;vy[cont]:=k;
        ux[cont]:=j;uy[cont]:=k;
      end;
    end;
    merge1(1,cont);merge2(1,cont);
    x1:=0;y1:=0;
    for i:=1 to m do begin
      readln(f,ch,nr);
      if ch='N' then begin
        poz1:=cauta1(1,cont,x1,y1);
        poz2:=cauta1(1,cont,x1,y1+nr);
        y1:=y1+nr;
        sum:=sum+poz2-poz1;
      end;
      if ch='S' then begin
        poz1:=cauta1(1,cont,x1,y1);
        poz2:=cauta1(1,cont,x1,y1-nr);
        if (vx[poz1]=x1) and (vy[poz1]=y1) then dec(poz1);
        y1:=y1-nr;
        sum:=sum+poz1-poz2;
      end;
      if ch='E' then begin
        poz1:=cauta2(1,cont,x1,y1);
        poz2:=cauta2(1,cont,x1+nr,y1);
        x1:=x1+nr;
        sum:=sum+poz2-poz1;
      end;
      if ch='V' then begin
        poz1:=cauta2(1,cont,x1,y1);
        poz2:=cauta2(1,cont,x1-nr,y1);
        if (ux[poz1]=x1) and (uy[poz1]=y1) then dec(poz1);
        x1:=x1-nr;
        sum:=sum+poz1-poz2;
      end;
    end;
  close(f);
  assign(f,'zc.out');rewrite(f);
    writeln(f,sum);
  close(f);
end.