1119D. Frets On Fire - Codeforces Solution C++

➤  Problem Link : 1119D. Frets On Fire 

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long int
 
int main()
{
  ll n,s;
  cin>>n;
  ll arr[100002];
  vector<ll> diff;
  ll p;
  long double cum[100002];
    for(ll i=0;i<n;i++)
    cin>>arr[i];
  sort(arr,arr+n);
  if(n!=1)
  {
 
      
      
      for(ll i=1;i<n;i++)
        diff.push_back(arr[i]-arr[i-1]);
      sort(diff.begin(),diff.end());
      
      p=diff.size();
      
    
      cum[0]=diff[0];
      for(ll i=1;i<p;i++)
        cum[i]=diff[i]+cum[i-1];
  }
    ll q,l,r;
      cin>>q;
      ll low,mid,high;
  while(q--)
  {
    cin>>l>>r;
    
    ll ans=r-l+1;
       
    if(n==1)
    {
        cout<<ans<< " ";
        continue;
    }
        
    low=0,high=p-1;
 
    while(low<high)
    {
      mid=low+(high-low)/2;
      if(diff[mid]>=ans)
        high=mid;
      else
        low=mid+1;
    }
    if(diff[low] < ans)
      ans+=cum[p-1];
    else
    {
      if(low!=0)
        ans+=ans*(p-low) + cum[low-1];
      else
        ans+=ans*(p-low);
    }
    cout<<ans<<" ";
 
  }
}

 

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook. 

😇Happy Learning!!

• Tweet
• Share
• Share
• Share
• Share

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.