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.