记录编号	266839	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]简单的区间问题	最终得分	100
用户昵称	ymxbiss	是否通过	通过
代码语言	C++	运行时间	0.030 s
提交时间	2016-06-09 21:04:02	内存使用	0.60 MiB

#include<stdio.h>
#include<algorithm>
inline void in(int&x){for(x=getchar();x<48|x>57;x=getchar());x^=48;for(int tmp=getchar();47<tmp&tmp<58;tmp=getchar())x=x*10+(tmp^48);}
inline int MAX(int A,int B){return A>B?A:B;}
int n,cnt,ans,f[20010];
struct line{int l,r;}o[10010];
inline bool cmp(const line&a,const line&b){return a.r<b.r;}
struct data{int x,id;}a[20010];
inline bool comp(const data&a,const data&b){return a.x<b.x;}
int main(){
	freopen("get_pos.in","r",stdin);
	freopen("get_pos.out","w",stdout);
	in(n);
	for(int i=0;i<n;++i)
		in(a[i<<1].x),in(a[i<<1|1].x),a[i<<1].id=a[i<<1|1].id=i;
	std::sort(a,a+n*2,comp);
	for(int i=0;i<2*n;++i){
		if(a[i].x!=a[i-1].x)++cnt;
		if(!o[a[i].id].l)o[a[i].id].l=cnt;
		else o[a[i].id].r=cnt;
	}
	std::sort(o,o+n,cmp);
	for(int i=1,j=0;i<=cnt;++i)
		for(f[i]=f[i-1];j<n&&o[j].r==i;++j)
			f[i]=MAX(f[i],f[o[j].l-1]+1);
	printf("%d\n",f[cnt]);
	for(int i=0;i<n;++i)
	    a[i<<1].x=o[i].l,a[i<<1].id=1,a[i<<1|1].x=o[i].r+1,a[i<<1|1].id=-1;
	std::sort(a,a+n*2,comp);
	for(int i=1,now=0,j=0;i<=cnt+1;++i){
		for(;j<2*n&&a[j].x==i;++j)
		    now+=a[j].id;
		ans=MAX(ans,now);
	}
	printf("%d",ans);
	//while(1);
}