PBCSEQ - Các đoạn nguyên
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
#include <cstdlib>
//#include <conio.h>
#define MAXM (100001)
struct dim
{
int w,h;
};
struct dim dims[MAXM];
int size[MAXM+1];
int anti_chain_size;
int cmp(const void *a,const void *b)
{
struct dim* ta=((struct dim*)a);
struct dim* tb=((struct dim*)b);
if (ta->w != tb->w)
return ta->w - tb->w;
return tb->h - ta->h;
}
int main(void)
{
//freopen("PBCSEQ.in","r",stdin);
int n,m,i,j;
scanf("%d",&m);
for (i=0;i<m;i++)
scanf("%d %d",&dims[i].w,&dims[i].h);
qsort(dims,m,sizeof(struct dim),cmp);
anti_chain_size=0;
for (i=0;i<m;i++)
{
int hi=anti_chain_size;
int lo=0;
while (hi>lo)
{
int mid=(hi+lo)/2;
if (size[mid]>=dims[i].h)
lo=mid+1;
else
hi=mid;
}
size[lo]=dims[i].h;
anti_chain_size+=(lo==anti_chain_size);
}
printf("%d\n",anti_chain_size);
// getch();
return 0;
}