Codeforces Round #350 (Div. 2)

Codeforces Round #350 (Div. 2)_D2

The term of this problem is the same as the previous one, the only exception — increased restrictions.

Input

The first line contains two positive integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 109) — the number of ingredients and the number of grams of the magic powder.

The second line contains the sequence a1, a2, ..., an (1 ≤ ai ≤ 109), where the i-th number is equal to the number of grams of the i-th ingredient, needed to bake one cookie.

The third line contains the sequence b1, b2, ..., bn (1 ≤ bi ≤ 109), where the i-th number is equal to the number of grams of the i-th ingredient, which Apollinaria has.

Output

Print the maximum number of cookies, which Apollinaria will be able to bake using the ingredients that she has and the magic powder.

Examples
input
1 1000000000
1
1000000000
output
2000000000
input
10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1 1 1 1 1
output
0
input
3 1
2 1 4
11 3 16
output
4
input
4 3
4 3 5 6
11 12 14 20
output
3题解：二分答案的经典应用

 1 #include<cstdio>
 2 #define LL long long
 3 #define FFC(i,a,b) for(int i=a;i<=b;i++)
 4 LL a[100010],b[100010],n,k,maxn=2*1e9+2;
 5 void fre(){freopen("c:\acm\input.txt","r",stdin);}
 6 LL search(LL l,LL r){
 7     LL mid,sum;
 8     while(l<=r){
 9         mid=(l+r)>>1,sum=0;
10         FFC(i,1,n){
11             sum+=a[i]*mid-b[i]>0?a[i]*mid-b[i]:0;
12             if(sum>k)break;//防爆LL
13         }
14         if(sum==k)return mid;
15         else if(sum<k)l=mid+1;
16         else r=mid-1;
17     }
18     return r;
19 }
20 int main(){
21     //fre();
22     while(~scanf("%I64d%I64d",&n,&k)){
23         FFC(i,1,n)scanf("%I64d",&a[i]);
24         FFC(i,1,n)scanf("%I64d",&b[i]);
25         printf("%I64d
",search(1,maxn));
26     }
27     return 0;
28 }

View Code