记录编号 102246 评测结果 AAAAAAAA
题目名称 挤牛奶 最终得分 100
用户昵称 Gravatar传奇 是否通过 通过
代码语言 Pascal 运行时间 0.007 s
提交时间 2014-05-17 21:04:29 内存使用 0.18 MiB
显示代码纯文本
program usaco1_2_1;
const
  maxn=5000;
type
  node2=^node3;
  node3=record
    l,r:longint;
    next:node2;
  end;
  node=record
    l,r:longint;
  end;
var
  a:array[1..maxn] of node;
  n,i:longint;
  head,p:node2;
procedure qp(l,r:longint);
var
  i,j,x:longint;
  y:node;
begin
  i:=l; j:=r;
  x:=a[(l+r) div 2].l;
  repeat
    while a[i].l>x do inc(i);
	while a[j].l<x do dec(j);
    if i<=j then
	  begin
	    y:=a[i];a[i]:=a[j];a[j]:=y;
		inc(i); dec(j);
	  end;
  until i>j;
  if l<j then qp(l,j);
  if i<r then qp(i,r);
end;
function max(a,b:longint):longint;
begin
  if a>b then exit(a)
  else exit(b);
end;
procedure hebing(q:node2);
begin
  while q^.next<>nil do
    begin
      if q^.r>=q^.next^.l then
        begin
	      q^.r:=max(q^.r,q^.next^.r);
	      q^.next:=q^.next^.next;
	    end
	  else
		  q:=q^.next;
    end;
end;
procedure find(q:node2);
var
  max1,max2,k:longint;
begin
  max1:=0;
  max2:=0;
  k:=q^.r;
  while q<>nil do
    begin
	  if q^.r-q^.l>max1 then
	    max1:=q^.r-q^.l;
	  if q^.l-k>max2 then
	    max2:=q^.l-k;
	  k:=q^.r;
	  q:=q^.next;
	end;
  writeln(max1,' ',max2);
end;
begin
  assign(input,'milk2.in');
  assign(output,'milk2.out');
  reset(input);
  rewrite(output);

  readln(n);
  for i:=1 to n do
    readln(a[i].l,a[i].r);
  qp(1,n);
  new(head);
  head^.next:=nil;
  for i:=1 to n do
    begin
	  new(p);
      p^.l:=a[i].l; p^.r:=a[i].r;
	  p^.next:=head^.next;
	  head^.next:=p;
    end;
  hebing(head^.next);
  find(head^.next);
	
  close(input);
  close(output);
end.