Зима '09: Условия задач (также содержат программы)

const MaxN = 100005; MaxK = 1000006;
type Integer = Longint;

var i, j, k, l, m, n: Integer;
  p, b, e: array [1..MaxN] of Integer;
  a: array [1..MaxK] of Integer;

function less (x, y: Integer): Boolean;
begin
  less := (e[x] < e[y]);
end;

procedure heapsort (N:integer);
var i, X, j, l, r: integer;
begin
  r := N;
  l := (N div 2)+1;
  repeat
    if l > 1 then begin l:=l-1; X := P[l] end
    else if r > 1 then begin X := P[r]; P[r] := P[1]; r:=r-1 end;
    j := l;
    repeat
      i := j;
      j := j*2;
      if (j < r) and less (P[j], P[j+1]) then j:=j+1;
      if (j > r) or not less (X, P[j]) then break;
      P[i] := P[j]
    until false;
    P[i] := X
  until r = 1;
end;

BEGIN
  read (n, k);
  if (n < 1) OR (n > 100000) then assert (False);
  if (k < 1) OR (k > 100) then assert (False);
  fillchar (a, sizeof (a), 0);
  fillchar (b, sizeof (b), 191);
  for i := 1 to n do begin
    read (b[i], e[i]);
    if (b[i] < 0) OR (b[i] > 1000000) then assert (False);
    if (e[i] < 0) OR (e[i] > 1000000) then assert (False);
    for j := b[i] + 1 to e[i] do begin
      inc (a[j]);
      if a[j] > k then assert (False);
    end;
  end;
  for i := 1 to n do p[i] := i;
  heapsort (n);
  l := 0;
  m := 0;
  for i := 1 to n do
    if b[p[i]] >= l then begin
      inc (m);
      l := e[p[i]];
    end;
  writeln (m);
END.

3 1
1 2
2 3
5 7

3

3 2
1 3
2 4
3 5

2

5 10
1 10
2 9
3 8
4 7
5 6

1

4 2
2 4
3 4
1 2
1 3

2