➤ Problem Link : 822C. Hacker, pack your bags!
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
struct voucher
{
ll l,r,cost;
ll suff,pre;
};
bool comp(voucher a, voucher b)
{
if(a.l != b.l)
return a.l < b.l;
else
return a.r < b.r ;
}
int main()
{
int n,x;
cin>>n>>x;
ll li,ri,ci;
voucher v;
map<ll,vector<voucher> > mp;
for(int i=0;i<n;i++)
{
cin>>li>>ri>>ci;
v.l=li;
v.r=ri;
v.cost=ci;
mp[ri-li+1].push_back(v);
}
ll low,mid,high;
ll ans=1000000000001;
for(auto it = mp.begin();it!=mp.end() ; it++)
{
// cout<<it->first<<" ";
ll d = x - it->first;
if(mp.find(d)==mp.end())
continue;
sort(mp[d].begin(),mp[d].end(),comp);
ll ssum=1000000000001,psum=1000000000001;
for(ll i=mp[d].size()-1;i>=0;i--)
{
if(mp[d][i].cost < ssum)
ssum = mp[d][i].cost;
mp[d][i].suff = ssum;
}
/* for(ll i=0;i<mp[d].size()-1;i++)
{
if(mp[d][i].cost < psum)
psum = mp[d][i].cost;
mp[d][i].pre = psum;
}*/
for(int i=0;i<it->second.size();i++)
{
low=0,high = mp[d].size();
ll cl = (it->second)[i].l;
ll cr = (it->second)[i].r;
// cout<<cl<<" "<<cr<<endl;
while(low<high)
{
mid=low+(high-low)/2;
if(mp[d][mid].l > cr)
high = mid;
else
low = mid+1;
}
if(low!=mp[d].size())
ans=min(ans,mp[d][low].suff+(it->second)[i].cost);
}
}
if(ans==1000000000001)
cout<<"-1";
else
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!!
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.