The term of this problem is the same as the previous one, the only exception — increased restrictions.
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.
Print the maximum number of cookies, which Apollinaria will be able to bake using the ingredients that she has and the magic powder.
1 1000000000
1
1000000000
2000000000
10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1 1 1 1 1
0
3 1
2 1 4
11 3 16
4
4 3
4 3 5 6
11 12 14 20
3
题目大意：就是制作一个蛋糕需要n种材料，然后你有k克魔法粉，每克魔法粉可以代替任意一克的材料,ai代表制作一个蛋糕需要第i种材料多少克，bi代表你拥有第i个材料多少克，问做多可以做多少个蛋糕。
题解:二分查找可以制作多少个蛋糕，假如可以制作，那么每一种材料都必须充足。
#include<stdio.h>
const int maxn= * 1e9 + ;
__int64 n, t, a[], b[];
__int64 f(__int64 z,__int64 y)
{
__int64 mid, sum;
int i;
while(z<=y)
{
mid=(z+y)/;
for(sum=,i=;i<=n;i++)
{
if(b[i]<a[i]*mid)
sum += (a[i]*mid-b[i]);
if(sum>t)
break;
}
if(sum==t)
return mid;
else if(sum<t)
z=mid+;
else
y=mid-;
}
return z-;
}
int main()
{
int i, j;
scanf("%d%d", &n, &t);
for(i=;i<=n;i++)
scanf("%d", &a[i]);
for(j=;j<=n;j++)
scanf("%d", &b[j]);
printf("%I64d\n", f(, maxn)); return ;
}