1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 #define MaxSize 500005
 5 struct trade{
 6     int x,y;
 7 };
 8 trade tp[MaxSize];
 9 int dp[MaxSize];//表示到第i個點時的可得到的最長不降單調序列
10 int num[MaxSize];//存儲輸入的序列
11 int n,m;
12 int cmp(trade a,trade b){
13     return a.x<b.x;
14 }
15 inline void scan(int &x){
16      char ch;
17      while (ch=getchar(),ch<'0'||ch>'9');x=ch-'0';
18      while (ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-'0';
19 }
20 int main(){
21     //freopen("in.txt","r",stdin);
22     int i,no=1;
23     while (~scanf("%d",&n)){
24         for(i=0;i<n;i++){//輸入交易
25             scan(tp[i].x);
26             scan(tp[i].y);
27         }
28         //sort(tp,tp+n,cmp);//排序，按第二梯隊查找最長不降單調子序列
29         memset(dp,0,sizeof(dp));
30         dp[0]=tp[0].y;
31         m=0;
32         for(i=1;i<n;i++){//二分的設計是難點 但思路其實很明了 
33             //為減小比較規模 應該利用dp數組 做每個可能序列的最大值存儲 這是時間優化關鍵
34             int mid,low=0,high=m;
35             while (low<=high){
36                 mid=(low+high)>>1;
37                 if(tp[i].y>dp[mid])
38                     low=mid+1;
39                 else
40                     high=mid-1;
41             }
42             dp[low]=tp[i].y;
43             if(low>m)
44                 m=low;
45         }    
46         printf("Case %d:\nMy king, at most %d %s can be built.\n\n",no++,m+1,m?"roads":"road");
47     }
48     return 0;
49 }
50