O - Magic Powder - 2

CodeForces - 670D2

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.

Example
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

题意：魔力粉作为混儿，一共能做多少饼干

解法：典型二分法，有最大范围，二分法求值

代码：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=100001;
ll a[maxn],b[maxn];
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        cin>>b[i];
    ll h=2000000000;
    ll l=0;
    ll ans=0;
    while(l<=h){
        ll k0=k;
        ll mid=(h+l)/2;
        int i;
        for(i=1;i<=n;i++){
            if(a[i]*mid>b[i])
                k0-=a[i]*mid-b[i];
            if(k0<0) break;
        }
        if(i-1==n){
            l=mid+1;
            ans=mid;
        }
        else
            h=mid-1;
    }
    cout<<ans<<endl;
}