1293: [SCOI2009]生日礼物 - BZOJ

  1 const
  2     maxn=1000010;
  3     maxk=65;
  4 type
  5     node=record
  6       x,k:longint;
  7     end;
  8 var
  9     a:array[0..maxn]of node;
 10     n,k:longint;
 11 
 12 operator <(a,b:node)c:boolean;
 13 begin
 14     c:=a.k<b.k;
 15 end;
 16 
 17 procedure swap(var x,y:node);
 18 var
 19     t:node;
 20 begin
 21     t:=x;x:=y;y:=t;
 22 end;
 23 
 24 procedure sort(l,r:longint);
 25 var
 26     i,j:longint;
 27     y:node;
 28 begin
 29     i:=l;
 30     j:=r;
 31     y:=a[(l+r)>>1];
 32     repeat
 33       while a[i]<y do
 34         inc(i);
 35       while y<a[j] do
 36         dec(j);
 37       if i<=j then
 38       begin
 39         swap(a[i],a[j]);
 40         inc(i);
 41         dec(j);
 42       end;
 43     until i>j;
 44     if i<r then sort(i,r);
 45     if j>l then sort(l,j);
 46 end;
 47 
 48 procedure init;
 49 var
 50     i,j,x:longint;
 51 begin
 52     read(k,k);
 53     for i:=1 to k do
 54       begin
 55         read(x);
 56         for j:=1 to x do
 57           begin
 58             inc(n);
 59             read(a[n].k);
 60             a[n].x:=i;
 61           end;
 62       end;
 63     sort(1,n);
 64 end;
 65 
 66 function flag(len:longint):boolean;
 67 var
 68     l,r,s:longint;
 69     cnt:array[0..maxk]of longint;
 70 begin
 71     l:=1;
 72     r:=0;
 73     s:=0;
 74     fillchar(cnt,sizeof(cnt),0);
 75     while  r<n do
 76       begin
 77         inc(r);
 78         inc(cnt[a[r].x]);
 79         if cnt[a[r].x]=1 then inc(s);
 80         while a[r].k-a[l].k>len do
 81           begin
 82             dec(cnt[a[l].x]);
 83             if cnt[a[l].x]=0 then dec(s);
 84             inc(l);
 85           end;
 86         if s=k then exit(true);
 87       end;
 88     exit(false);
 89 end;
 90 
 91 procedure work;
 92 var
 93     l,r,mid:longint;
 94 begin
 95     l:=0;
 96     r:=a[n].k-a[1].k;
 97     while l<>r do
 98       begin
 99         mid:=longint((int64(l)+r)>>1);
100         if flag(mid) then r:=mid
101         else l:=mid+1;
102       end;
103     write(l);
104 end;
105 
106 begin
107     init;
108     work;
109 end.