Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const fi='';
var test,it,n,re:longint;
    a,b,f:array[1..20000] of longint;

procedure sort(l,r:longint);
var i,j,x,y,t:longint;
begin
     i:=l; j:=r; x:=a[(i+j) shr 1]; y:=b[(i+j) shr 1];
     repeat
           while (a[i]<x) or ((a[i]=x) and (b[i]>y)) do inc(i);
           while (a[j]>x) or ((a[j]=x) and (b[j]<y)) do dec(j);
           if i<=j then
           begin
                t:=a[i]; a[i]:=a[j]; a[j]:=t;
                t:=b[i]; b[i]:=b[j]; b[j]:=t;
                inc(i); dec(j);
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

procedure rf;
var i:longint;
begin
     read(n);
     for i:=1 to n do read(a[i],b[i]);
     sort(1,n);
end;

function bs(x:longint):longint;
var l,r,m,i:longint;
begin
     l:=1; r:=re;
     while l<=r do
     begin
          m:=(l+r) shr 1;
          if f[m]<x then r:=m-1
          else l:=m+1;
     end;
     for i:=m-1 to m+1 do
          if (i>0) and (i<=re) and (f[i]<x) then exit(i);
end;

procedure pr;
var i,x:longint;
begin
     re:=1; f[1]:=b[1];
     for i:=2 to n do
         if b[i]<=f[re] then
         begin
              re:=re+1; f[re]:=b[i];
         end
         else
         begin
              x:=bs(b[i]);
              f[x]:=b[i];
         end;
     writeln(re);
end;

begin
     assign(input,fi); reset(input);
     read(test);
     for it:=1 to test do
     begin
          rf;
          pr;
     end;
     close(input);
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 20000 + 5;
pair<int, int> a[N];
int n, lst[N];


void enter() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d%d", &a[i].first, &a[i].second);
}
const bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
    return a.first == b.first ? a.second > b.second : a.first < b.first;
}

void solve() {
    sort(a, a+n, cmp); int res = 0;
    for(int i = n-1; i >= 0; --i) {
        int dp = upper_bound(lst, lst+res, a[i].second) - lst;
        if(dp == res) ++res, lst[dp] = a[i].second;
        else lst[dp] = min(lst[dp], a[i].second);
    }
    printf("%d\n", res);
}

int main() {
    int tc; scanf("%d", &tc);
    while(tc--) enter(), solve();
    return 0;
}

Code mẫu của ladpro98

uses    math;
type    e=record
        l,r:longint;
        end;
const   fi='';
        maxN=22222;
var     a:array[1..maxN] of e;
        f:array[1..maxN] of longint;
        tt,t,n,d:longint;
        inp:text;

procedure openF;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,t);
end;

procedure input;
var     i:longint;
begin
        readln(inp,n);
        for i:=1 to n do
        read(inp,a[i].l,a[i].r);

end;

procedure swap(i,j:longint);
var     t:e;
begin
        t:=a[i];
        a[i]:=a[j];
        a[j]:=t;
end;

procedure sort(l,r:longint);
var     p:e;
        i,j:longint;
begin
        if l>=r then exit;
        p:=a[random(r-l+1)+l];
        i:=l;j:=r;
        repeat
                while (a[i].l<p.l) or ((a[i].l=p.l) and (a[i].r>p.r)) do inc(i);
                while (a[j].l>p.l) or ((a[j].l=p.l) and (a[j].r<p.r)) do dec(j);
                if i<=j then
                begin
                        if i<j then swap(i,j);
                        inc(i);dec(j);
                end;
        until i>j;
        sort(l,j);sort(i,r);
end;


function find(r:longint; key:e):longint;
var     l,m,k:longint;
begin
        l:=1;
        while l<=r do
        begin
                m:=(l+r) shr 1;
                if (a[f[m]].l<key.l) and (a[f[m]].r<key.r) then
                begin
                        k:=m;
                        r:=m-1;
                end
                else l:=m+1;
        end;
        exit(k);
end;

procedure dp;
var     i:longint;
begin
        f[1]:=1;
        d:=1;
        for i:=2 to n do
        begin
                if (a[i].r<=a[f[d]].r) or (a[i].l<=a[f[d]].l) then
                begin
                        inc(d);
                        f[d]:=i;
                end
                else
                f[find(d,a[i])]:=i;
        end;
end;

begin
        openF;
        for tt:=1 to t do
        begin
                input;
                sort(1,n);
                dp;
                writeln(d);
        end;
end.

Code mẫu của RR

{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=20111;
var
  f1,f2:text;
  c,a,b:array[1..MAXN] of longint;
  sl,n,test: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,a[i],b[i]);
end;
procedure swap(var a,b:longint);
var temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure sort(l,r:longint); inline;
var
  i,j,ma,mb,key:longint;
begin
  key:=random(r-l+1)+l;
  i:=l; j:=r; mb:=b[key]; ma:=a[key];
  repeat
    while (b[i]<mb) or ((b[i]=mb) and (a[i]>ma)) do inc(i);
    while (b[j]>mb) or ((b[j]=mb) and (a[j]<ma)) do dec(j);
    if i<=j then
      begin
        swap(a[i],a[j]);
        swap(b[i],b[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;
var
  l,r,mid,kq:longint;
begin
  l:=1; r:=sl;
  repeat
    mid:=(l+r)>>1;
    if c[mid]<key then
      begin
        kq:=mid;
        r:=mid-1;
      end
    else l:=mid+1;
  until l>r;
  exit(kq);
end;
procedure solve;
var
  u,i:longint;
begin
  sl:=1; c[1]:=a[1];
  for i:=2 to n do
    if a[i]<=c[sl] then
      begin
        inc(sl);
        c[sl]:=a[i];
      end
    else
      begin
        u:=find(a[i]);
        c[u]:=a[i];
      end;
end;
begin
  openF;
  read(f1,test);
  for test:=1 to test do
    begin
      inp;
      sort(1,n);
      solve;
      writeln(f2,sl);
    end;
  closeF;
end.

Code mẫu của hieult

#include <stdio.h>
#include <cstdlib>
#include <algorithm>
//#include <conio.h>

using namespace std;

struct doll{
    int rong,cao;
};

doll A[22222];
int f[22222],test,n,so;
/*
int cmp(const void *a,const void *b)
{
   doll  ta= *( doll*)a;
   doll  tb= *( doll*)b;


  if (ta.rong == tb.rong)
  return tb.cao  - ta.cao;
    return ta.rong - tb.rong;
  //return tb->cao  - ta->cao;

}
*/
int cmp(const void *a,const void *b)
{
    doll X = *( doll*)a;
    doll Y = *( doll*)b;
    if(X.rong==Y.rong) return Y.cao-X.cao;
    return X.rong - Y.rong;
}

int main()
{
   // freopen("MDOLLS.in","r",stdin);
    scanf("%d",&test);
    while(test--){
        scanf("%d",&n);
        for(int i = 0;i<n;i++) scanf("%d %d",&A[i].rong,&A[i].cao);
       // memset(f,0,sizeof(f));
        qsort(A,n,sizeof(struct doll),cmp);
        so = 0;
        int be,lon;
        for(int i = 0;i<n;i++){
             be = 0;
             lon = so;
             while(lon>be)
             {
                  int tb = (lon+be)/2;
                  if(f[tb]>=A[i].cao)
                      be = tb+1;
                  else lon = tb;
             }
             f[be] = A[i].cao;
             so += (be==so);
        }
        printf("%d\n",so);
    }
   // getch();
}

Code mẫu của ll931110

Program MDOLLS;
  Const
    input  = '';
    output = '';
    maxn = 20000;
  Type
    rec = record
      h,w: integer;
    end;
  Var
    a,s: array[1..maxn] of rec;
    t,m,n,i: integer;
    fi,fo: text;

Procedure openfile;
  Begin
    Assign(fi, input);
      Reset(fi);

    Assign(fo, output);
      Rewrite(fo);
  End;

Procedure init;
  Var
    i: integer;
  Begin
    Readln(fi, m);
    For i:= 1 to m do read(fi, a[i].w, a[i].h);
  End;

Procedure swap(var x,y: rec);
  Var
    z: rec;
  Begin
    z:= x;
    x:= y;
    y:= z;
  End;

Procedure quicksort;

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

      i:= low;
      j:= high;

      k:= random(high - low + 1) + low;
      p:= a[k].w;
      q:= a[k].h;

      Repeat
        While (a[i].w > p) or ((a[i].w = p) and (a[i].h < q)) do inc(i);
        While (a[j].w < p) or ((a[j].w = p) and (a[j].h > q)) 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;

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

  Begin
    partition(1,m);
  End;

Procedure update(i: integer);
  Var
    inf,sup,med,r: integer;
  Begin
    r:= 0;
    inf:= 1;
    sup:= n;

    Repeat
      med:= (inf + sup) div 2;
      If (s[med].w > a[i].w) and (s[med].h > a[i].h) then
        Begin
          r:= med;
          sup:= med - 1;
        End
      else inf:= med + 1;
    Until inf > sup;

    If r = 0 then
      Begin
        inc(n);
        r:= n;
      End;

    s[r].w:= a[i].w;
    s[r].h:= a[i].h;
  End;

Procedure solve;
  Var
    i: integer;
  Begin
    n:= 1;
    with s[1] do
      Begin
        h:= a[1].h;
        w:= a[1].w;
      End;

    For i:= 2 to m do update(i);
    Writeln(fo, n);
  End;

Procedure closefile;
  Begin
    Close(fo);
    Close(fi);
  End;

Begin
  openfile;

  Readln(fi, t);
  For i:= 1 to t do
    Begin
      init;
      quicksort;
      solve;
    End;

  closefile;
End.

Code mẫu của khuc_tuan

#include <iostream>
#include <set>
using namespace std;

int n;
pair<int,int> a[20200];

int main() {
    int st;
    scanf("%d", &st);
    for(int t=0;t<st;++t) {
        scanf("%d", &n);    
        for(int i=0;i<n;++i)
            scanf("%d%d", &a[i].first, &a[i].second);
        sort( a, a+n);
        multiset<int> se;
        for(int i=0;i<n;++i) if(i==0 || a[i].first != a[i-1].first) {
            for(int j=i;j<n && a[j].first==a[i].first;++j) {
                multiset<int>::iterator p = se.lower_bound(a[j].second);
                if(p!=se.begin()) {
                    --p;
                    se.erase(p);    
                }
            }   
            for(int j=i;j<n && a[j].first==a[i].first;++j) se.insert(a[j].second);
        }
        cout << se.size() << endl;
    }   
    return 0;
}