729C. Road to Cinema - Codeforces Solution C++ ~ CodingWithArt

➤ Problem Link : 729C. Road to Cinema

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long int
vector< pair<ll,ll> > arr;
bool func(ll v, ll pos[], ll k,ll t)
{
  ll d,x,curr=0;
  ll time=0;
  for(ll i=0;i<k;i++)
  {
    d=pos[i]-curr;
    curr=pos[i];
    if(d>v)
      return 0;
    x=min(d,v-d);
    time+=x+2*(d-x);
    if(time>t)
      return 0;
  }
  return 1;
}
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll n,k,s,t;
  cin>>n>>k>>s>>t;
 
  ll minN[n];
  ll c,v;
  for(ll i=1;i<=n;i++)
  {
    cin>>c>>v;
    arr.push_back(make_pair(v,c));
  }
  ll pos[k+1];
  for(ll i=0;i<k;i++)
    cin>>pos[i];
  pos[k]=s;
 
  sort(pos,pos+k+1);
  sort(arr.begin(),arr.end());
 
  minN[n-1]=arr[n-1].second;
  for(ll i=n-2;i>=0;i--)
    minN[i]=min(arr[i].second,minN[i+1]);
 
  ll low=0,high=arr[n-1].first+5,mid;
 
  while(low<high)
  {
    mid=low+(high-low)/2;
    if(func(mid,pos,k+1,t))
      high=mid;
    else
      low=mid+1;
  }
  ll ans=low;
 
  low=0,high=arr.size()-1;
  while(low<high)
  {
    mid=low+(high-low)/2;
    if(arr[mid].first>=ans)
      high=mid;
    else
      low=mid+1;
  }
  if(arr[low].first < ans)
    cout<<"-1";
  else
    cout<<minN[low];
 
}

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!!

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.