Bike Racing

Bike Racing

A Bike race is to be organized. There will be N bikers. You are given initial Speed of the ith Biker by Hi Km/hr and the Acceleration of ith biker as Ai Km/Hr².

The organizers want the safety of the bikers and the viewers.They monitor the Total Speed on the racing track after every Hour.
A biker whose Speed is 'L' or more, is considered a Fast Biker.
To Calculate the Total speed on the track- They Add the speed of each Fast biker ,at that Hour. 
As soon as The total speed on the track is 'M' KiloMeters per Hour or more, The safety Alarm buzzes.
You need to tell what is the minimum number of Hours after which the safety alarm will buzz.

Constraints:
1<=T<=100
1<=N<=1e5
1 ≤ M,L ≤ 1e10
1 ≤ Hi, Ai ≤ 1e9

Explanation:
Sample Input:
1
3 400 120
20 20
50 70
20 90

Sample Output:
3

Explanation:
Speeds of all the Bikers at ith Minute
Biker1= 20 40 60 80 100 120 
Biker2= 50 120 190 260 330
Biker3= 20 110 200 290 380 

Total Initial speeds = 0 (Because none of the biker's speed is fast enough)
total Speed at 1st Hour= 120
total Speed at 2nd Hour= 190+200=390
total Speed at 3rd Hour= 260+290=550
Alarm will buzz at 3rd Hour.

There are N Bikers. The initial Speed of the ith Biker is Hi Kilo Meters per Hour, and the Acceleration is Ai Kilo Meters per Hour.

What is the fewest number of Hours before the Total speed of all the bikers is greater than equal to M Kilo Meters per Hour?

The Brute force solution for this is to just loop through the number of Hours, say T, and then check if at this Hour, will the alarm Buzz.
Checking is Easy: For each biker , its speed after T Hours is Hi+ Ai*T.
But this would result in TLE verdict. Because The constraint for M is 1e10.

So, We need to observe something. Once we have Observed this , Then The Problem Breaks.
If we have enough Total speed on the track at time instant T, Then surely, we will also have enough speed at time T+1 and at T+2....any time instant greater than T.

That means, Speed of the bikes increases with Increase in time.
So, it is a monotonic function. Thus We can apply Binary Search.

Another Optimization Necessary for AC.
Now, For a given time instant To calculate the total speed on the track , You can iterate for all bikes and calculate its speed by Hi + T*Ai. 
Works in O(N).
 

PS: Take care of Overflows, as it may occur. 64-bit integers can be Overflown easily as we are playing with Large integers in this problem.

#include <bits/stdc++.h>
using namespace std;
int a[100000],u[100000];
long int tracksp(long int h,long int l,long int m,int n)
{
      long int st=0,x=0;
              for(int i=0;i<n;++i)
              {
                  x=(u[i]+h*a[i]);
                  if(l<=x)st=st+x;
                  if(st>=m)
                  return m;
              }
              return st;
   
}
int main() {
    //code
    int t;
    cin>>t;
    while(t--)
    {
        long int m,l;
        int n;
        cin>>n>>m>>l;
        a[n],u[n];
        for(int i=0;i<n;++i)
        {
            cin>>u[i]>>a[i];
        }
        long int low=0,high=1e10;
        while(low<high)
        {   
            long int mid=(low+high)/2;
            long int val=tracksp(mid,l,m,n);
            if(val>=m)high=mid;
            else
            low=mid+1;
        }
        cout<<high<<'\n';
    }
    return 0;
}