PBCSEQ - Các đoạn nguyên

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
Program PBCSEQ;
  Const
    input  = '';
    output = '';
    maxn = 100000;
  Var
    a,b,L,Start: array[0..maxn + 1] of integer;
    n,m: integer;

Procedure init;
  Var
    f: text;
    i: integer;
  Begin
    Assign(f, input);
      Reset(f);

    Readln(f, n);
    For i:= 1 to n do read(f, a[i], b[i]);

    Close(f);
  End;

Procedure swap(var x,y: integer);
  Var
    t: integer;
  Begin
    t:= x;
    x:= y;
    y:= t;
  End;

Procedure quicksort;

  Procedure partition(low,high: integer);
    Var
      i,j,p,p1,p2: integer;
    Begin
      If low >= high then exit;

      i:= low;
      j:= high;
      p:= random(high - low + 1) + low;

      p1:= a[p];
      p2:= b[p];

      Repeat
        While (b[i] > p2) or ((b[i] = p2) and (a[i] < p1)) do inc(i);
        While (b[j] < p2) or ((b[j] = p2) and (a[j] > p1)) do dec(j);

        If i <= j then
          Begin
            if i < j then
              Begin
                swap(a[i],a[j]);
                swap(b[i],b[j]);
              End;

            inc(i);
            dec(j);
          End;
      Until i > j;

      partition(low,j);
      partition(i,high);
    End;

  Begin
    partition(1,n);
  End;

Procedure enter;
  Begin
    a[0]:= low(integer);
    a[n + 1]:= high(integer);

    m:= 1;
    L[n + 1]:= 1;
    Start[1]:= n + 1;
  End;

Function Find(i: integer): integer;
  Var
    inf,sup,med,j: integer;
  Begin
    inf:= 1;
    sup:= m + 1;

    Repeat
      med:= (inf + sup) div 2;
      j:= Start[med];

      If a[j] >= a[i] then inf:= med else sup:= med;
    Until inf + 1 = sup;

    Find:= Start[inf];
  End;

Procedure optimize;
  Var
    i,j,k: integer;
  Begin
    For i:= n downto 0 do
      Begin
        j:= Find(i);
        k:= L[j] + 1;

        If k > m then
          Begin
            m:= k;
            Start[k]:= i;
          End
        else
          if a[Start[k]] <= a[i] then Start[k]:= i;

        L[i]:= k;
      End;
  End;

Procedure printresult;
  Var
    f: text;
    i: integer;
  Begin
    Assign(f, output);
      Rewrite(f);
      Writeln(f, m - 2);
    Close(f);
  End;

Begin
  init;
  quicksort;
  enter;
  optimize;
  printresult;
End.

Download