NKBUS - Bus

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
program NKBUS;
const
  input  = '';
  output = '';
  maxn = 200001;
var
  n,m,res,num: integer;
  a,st,t,d: array[1..maxn] of integer;

procedure init;
var
  f: text;
  i,j,num: integer;
begin
  assign(f, input);
    reset(f);

  readln(f, n, m);
  st[1] := 1;

  for i := 1 to n do
    begin
      read(f, d[i], num);
      for j := 0 to num - 1 do read(f, a[st[i] + j]);
      st[i + 1] := st[i] + num;
    end;

  close(f);
end;

procedure swap(var x,y: integer);
var
  z: integer;
begin
  z := x;  x := y;  y := z;
end;

procedure qsort(l,h: integer);
var
  i,j,p: integer;
begin
  if l >= h then exit;
  i := l;  j := h;  p := a[random(h - l + 1) + l];

  repeat
    while a[i] < p do inc(i);
    while a[j] > p do dec(j);

    if i <= j then
      begin
        if i < j then swap(a[i],a[j]);
        inc(i);
        dec(j);
      end;
  until i > j;

  qsort(l,j);
  qsort(i,h);
end;

function calc(i: integer): integer;
var
  inf,sup,med,k: integer;
begin
  inf := st[i];
  sup := st[i + 1] - 1;
  if inf > sup then exit(0);
  if a[inf] > t[i] then exit(0);

  repeat
    med := (inf + sup) div 2;
    if a[med] > t[i] then sup := med - 1 else
      begin
        k := med;
        inf := med + 1;
      end;
  until inf > sup;

  calc := k - st[i] + 1;
end;

function intime(x: integer): boolean;
var
  i,tot: integer;
begin
  t[n + 1] := x;
  for i := n downto 1 do t[i] := t[i + 1] - d[i];
  if d[1] < 0 then exit(false);

  tot := 0;
  for i := 1 to n do tot := tot + calc(i);
  intime := tot >= num;
end;

procedure solve;
var
  i,sum: integer;
  inf,sup,med: integer;
begin
  if st[n + 1] > m then num := m else num := st[n + 1] - 1;
  for i := 1 to n do qsort(st[i],st[i + 1] - 1);

  sum := 0;
  for i := 1 to n do sum := sum + d[i];

  inf := sum;
  sup := high(integer);

  repeat
    med := (inf + sup) div 2;
    if not intime(med) then inf := med + 1 else
      begin
        res := med;
        sup := med - 1;
      end;
  until inf > sup;
end;

procedure printresult;
var
  f: text;
begin
  assign(f, output);
    rewrite(f);
    writeln(f, res);
  close(f);
end;

begin
  init;
  solve;
  printresult;
end.

Download