#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int maxn=1e5+10; int n,n1,n2,a[maxn][2],b[maxn][2]; int p[maxn],t,ans; int fr(){ char ch=getchar(); while(ch>'9'||ch<'0') ch=getchar(); int sum=ch-'0'; while((ch=getchar())>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+ch-'0'; return sum; } int main() { n=fr(); int x,y; for(int i=1;i<=n;i++){ x=fr(); y=fr(); if(x<y){ a[++n1][0]=x; a[n1][1]=y; } if(x>y){ b[++n2][0]=x; b[n2][1]=y; } } p[++t]=a[1][1]; for(int i=2;i<=n1;i++){ if(a[i][0]<p[t]) p[++t]=a[i][1]; else if(a[i][1]>p[t]&&(t==1||p[t-1]>a[i][0])){ t--; p[++t]=a[i][1]; } } ans=t; t=0; p[++t]=b[1][1]; for(int i=2;i<=n2;i++){ if(b[i][0]>p[t]) p[++t]=b[i][1]; else if(b[i][1]<p[t]&&(t==1||p[t-1]<b[i][0])){ t--; p[++t]=b[i][1]; } } ans=max(ans,t); printf("%d",ans); return 0; }
全部评论
(0) 回帖