Cod sursa(job #25116)

Utilizator alex_damianDamian Alexandru alex_damian Data 4 martie 2007 10:51:53
Problema Ograzi Scor 0
Compilator fpc Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 1.94 kb
type rec = record
  x, y: longint;
  sgn: integer;
end;

var t:array[0..1048576] of word;
  a, aux:array[0..150000] of rec;
  i, j, n, m, w, h, x, y, v, q, res: longint;
  f,g: text;


procedure sort(l,r:longint);
var mij, p1, p2, p, i:longint;
begin
mij:=(l+r) div 2;
if (l<r) then begin
  sort(l, mij);
  sort(mij+1, r);
  p1:=l; p2:=mij+1; p:=l;
  while (p1<=mij) and (p2<=r) do begin
    if (a[p1].x<a[p2].x) then begin aux[p]:=a[p1]; inc(p1); inc(p); end
    else if (a[p1].x=a[p2].x) and (a[p1].sgn>a[p2].sgn) then begin aux[p]:=a[p1]; inc(p1); inc(p); end
    else begin aux[p]:=a[p2]; inc(p); inc(p2); end;
  end;
  for i:=p1 to mij do begin aux[p]:=a[i]; inc(p); end;
  for i:=p2 to r do begin aux[p]:=a[i]; inc(p); end;
  for i:=l to r do a[i]:=aux[i];
end;
end;

function max(x,y:longint):longint;
begin
if (x>y) then max:=x else max:=y;
end;


function query(n,l,r,a,b:longint):longint;
var m, tt: longint;
begin
tt:=0;
if (a<=l) and (r<=b) then tt:=t[n]
else begin
  m:= (l+r) div 2;
  if (a<=m) then tt:=tt+query(2*n, l, m, a, b);
  if (b>m) then tt:=tt+query(2*n+1, m+1, r, a, b);
end;
query:=tt;
end;

procedure act(n,l,r,p,v:longint);
var m:longint;
begin
m:= (l+r) div 2;
inc(t[n], v);
if (l<r) then begin
  if (p<=m) then act(2*n, l, m, p, v)
  else act(2*n+1, m+1, r, p, v);
end;
end;


begin
assign(f,'ograzi.in');reset(f);
assign(g,'ograzi.out');rewrite(g);
readln(f, n, m, w, h);
v:=0;
for i:=1 to n do begin
  inc(v);
  readln(f, a[v].x, a[v].y);
  a[v].sgn:=1;
  inc(v);
  a[v].y:=a[v-1].y;
  a[v].x:=a[v-1].x+w;
  a[v].sgn:=-1;
end;
for i:=1 to m do begin
  inc(v);
  readln(f, a[v].x, a[v].y);
  a[v].sgn:= 0;
end;
sort(1,v);

for i:=1 to v do begin
  if (a[i].sgn = 0) then begin
    q:= query(1, 0, 1000000, max(a[i].y-h, 0), a[i].y);
    if (q<>0) then inc(res);
  end
  else act(1,0, 1000000, a[i].y, a[i].sgn);
end;
writeln(g,res);
close(f);
close(g);
end.