1 /* 2 TLE 3 */ 4 #include <iostream> 5 #include <cstdio> 6 #include <cstring> 7 using namespace std; 8  9 const int maxn=5e5+5;10 int a[maxn],b[maxn],c[maxn],f[maxn<<1];11 inline int max(int a,int b){return a>b?a:b;}12 void swap(int &a,int &b){int t=a;a=b;b=t;}13 void qsort(int l,int r)14 {15     if(l<r)16     {17         int key=b[l],i=l,j=r;18         while(i!=j)19         {20             while(b[j]>=key && i<j) j--;21             while(b[i]<=key && i<j) i++;22             if(i<j) swap(b[i],b[j]);23         }24         b[l]=b[i];b[i]=key;25         qsort(l,i-1);26         qsort(i+1,r);27     }28 }29 int binary_search(int l,int r,int val)30 {31     int mid;32     while(l<=r)33     {34         mid=(l+r)>>1;35         if(c[mid]>val) r=mid-1;36         else if(c[mid]==val) return mid;37         else l=mid+1;38     }39     return -1;40 }41 void updata(int pos,int v,int l,int r,int rt)42 {43     if(l==r)44     {45         f[rt]=v;return;46     }47     int mid=(l+r)>>1;48     if(pos<=mid) updata(pos,v,l,mid,rt<<1);49     else updata(pos,v,mid+1,r,rt<<1|1);50 }51 int query(int L,int R,int l,int r,int rt)52 {53     if(L<=l && r<=R)54         return f[rt];55     int mid=(l+r)>>1;56     int ans;57     if(L<=mid) ans=query(L,R,l,mid,rt<<1);58     if(R>mid) ans=max(ans,query(L,R,mid+1,r,rt<<1|1));59     return ans;60 }61 int main()62 {63     int icase=0,n,tmp,i,cnt;64     while(~scanf("%d",&n))65     {66         for(i=1;i<=n;i++) 67         {68             scanf("%d%d",&tmp,a+i);b[i]=a[i];69         }70         qsort(1,n);cnt=1;c[1]=b[1];71         for(i=2;i<=n;i++)72             if(b[i]!=b[i-1])73                 c[++cnt]=b[i];74         memset(f,0,sizeof(f));75         int ans=0,maxv,x;76         for(i=1;i<=n;i++)77         {78             x=binary_search(1,cnt,a[i]);79             if(x>1) maxv=query(1,x-1,1,cnt,1);80             else maxv=0;81             updata(x,maxv+1,1,cnt,1);82             if(maxv+1>ans) ans=maxv+1;83         }84         printf("Case %d:\n",++icase);85         if(ans==1) printf("My king, at most 1 road can be built.\n\n");86         else printf("My king, at most %d roads can be built.\n\n",ans);87     }88     return 0;89 }90 /*91 292 1 293 2 194 395 1 296 2 397 3 198 */

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5  6 const int maxn=5e+5; 7 int dp[maxn],f[maxn]; 8  9 int upper_bound(int l,int r,int val)//二分求上界10 {11     int mid,ans=-1;12     while(l<=r)13     {14         mid=(l+r)>>1;15         if(dp[mid]>=val) ans=mid,r=mid-1;16         else l=mid+1;17     }18     return ans;19 }20 21 int main()22 {23     int icase=0,n,i,cnt,x,y;24     while(~scanf("%d",&n))25     {26         for(i=1;i<=n;i++)27         {28             scanf("%d%d",&x,&y);29             f[x]=y;30         }31         dp[1]=f[1];cnt=1;32         for(i=1;i<=n;i++)33         {34             x=upper_bound(1,cnt,f[i]);35             if(x==-1) dp[++cnt]=f[i];36             else dp[x]=f[i];37         }38         printf("Case %d:\n",++icase);39         if(cnt==1) printf("My king, at most 1 road can be built.\n\n");40         else printf("My king, at most %d roads can be built.\n\n",cnt);41     }42     return 0;43 }