MCONVOI - Con Voi

Tác giả: RR

Ngôn ngữ: Pascal

//Written by RR

{$MODE OBJFPC}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       300111;
  base          =       1000000007;

var
  f1,f2         :       text;
  n,d           :       longint;
  x,y,f,reg     :       array[0..MAXN] of longint;
  last,sl,ind   :       array[1..MAXN] of longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;

procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure inp;
    var
      i:longint;
    begin
      read(f1,n);
      for i:=1 to n do
        read(f1,x[i],y[i]);
    end;

procedure swap(var a,b:longint); inline;
    var
      tmp:longint;
    begin
      tmp:=a; a:=b; b:=tmp;
    end;

procedure sort(l,r:longint); inline;
    var
      i,j,mx,my,key:longint;
    begin
      i:=l; j:=r; key:=l+random(r-l+1);
      mx:=x[key]; my:=y[key];
      repeat
        while (y[i]<my) or ((y[i]=my) and (x[i]>mx)) do inc(i);
        while (y[j]>my) or ((y[j]=my) and (x[j]<mx)) do dec(j);
        if i<=j then
          begin
            swap(x[i],x[j]);
            swap(y[i],y[j]);
            inc(i); dec(j);
          end;
      until i>j;
      if i<r then sort(i,r);
      if l<j then sort(l,j);
    end;

function find(key:longint):longint; inline;
    var
      res,l,r,mid:longint;
    begin
      res:=0; l:=1; r:=d;
      while (l<=r) do
        begin
          mid:=(l+r)>>1;
          if last[mid]<key then
            begin
              res:=mid;
              l:=mid+1;
            end
          else r:=mid-1;
        end;
      exit(res);
    end;

function find1(l,r,key:longint):longint; inline;
    var
      mid,res:longint;
    begin
      res:=r;
      while (l<=r) do
        begin
          mid:=(l+r)>>1;
          if last[mid]<key then
            begin
              res:=mid;
              r:=mid-1;
            end
          else l:=mid+1;
        end;
      exit(res);
    end;

function find2(l,r,key:longint):longint; inline;
    var
      mid,res:longint;
    begin
      res:=l;
      while (l<=r) do
        begin
          mid:=(l+r)>>1;
          if ind[mid]<key then
            begin
              res:=mid;
              l:=mid+1;
            end
          else r:=mid-1;
        end;
      exit(res);
    end;

procedure solve;
    var
      i,k,u,v:longint;
    begin
      //Tinh do dai day con tang dai nhat
      d:=0;
      for i:=1 to n do
        begin
          k:=find(x[i]);
          f[i]:=k+1;
          d:=max(d,k+1);
          last[k+1]:=x[i];
          inc(sl[k+1]);
        end;
      writeln(f2,d);

      //Dem phan phoi
      for i:=2 to d do
        sl[i]:=sl[i-1]+sl[i];

      for i:=n downto 1 do
        begin
          last[sl[f[i]]]:=x[i];
          ind[sl[f[i]]]:=i;
          reg[sl[f[i]]]:=f[i];
          dec(sl[f[i]]);
        end;

      //Dem so luong
      fillchar(f,sizeof(f),0);
      f[1]:=1;
      for i:=2 to n do
      if reg[i]=1 then f[i]:=f[i-1]+1
      else
        begin
          u:=find1(sl[reg[i]-1]+1,sl[reg[i]],last[i]);
          v:=find2(sl[reg[i]-1]+1,sl[reg[i]],ind[i]);

          if reg[u-1]+2=reg[i] then f[u-1]:=0;
          if u>v then f[i]:=1
          else f[i]:=f[v]-f[u-1]; if f[i]<0 then inc(f[i],base);

          if (i<>sl[reg[i]]+1) then
            begin
                f[i]:=(f[i-1]+f[i]);
                if f[i]>base then dec(f[i],base);
            end;
        end;
      writeln(f2,f[n]);
    end;

begin
  openF;
  inp;
  sort(1,n);
  solve;
  closeF;
end.

Download