fork download
  1. #include<bits/stdc++.h>
  2. #define ll long long int
  3. using namespace std;
  4. int main()
  5. {
  6. ll n,k,u,v,w,days;
  7. cin>>n>>k;
  8. vector<pair<ll,pair<ll,ll> > > deal;//(w,(u,v))
  9. vector<pair<ll,ll> > pack[k];
  10. vector<ll> pack1[k],pack2[k];
  11. for(ll i=0;i<n;i++)
  12. {
  13. cin>>u>>v>>w;
  14. days=v-u+1;
  15. if(days>=k)
  16. continue;
  17. deal.push_back({w,{u,v}});
  18. pack[days].push_back({u,w});
  19. }
  20. for(ll i=0;i<k;i++)
  21. sort(pack[i].begin(),pack[i].end());
  22. for(ll i=0;i<k;i++)
  23. {
  24. for(ll j=0;j<pack[i].size();j++)
  25. {
  26. pack1[i].push_back(pack[i][j].first);
  27. pack2[i].push_back(pack[i][j].second);
  28. }
  29. ll mini=1e18;
  30. if(pack2[i].size()==0)
  31. continue;
  32. for(ll j=pack2[i].size()-1;j>=0;j--)
  33. {
  34. mini=min(mini,pack2[i][j]);
  35. pack2[i][j]=mini;
  36. }
  37. }
  38. ll ans=1e18;
  39. for(ll i=0;i<deal.size();i++)
  40. {
  41. ll cost=deal[i].first;
  42. u=deal[i].second.first;
  43. v=deal[i].second.second;
  44. days=v-u+1;
  45. ll left=k-days;
  46. days=left;
  47. //search in pack1[days]
  48. v++;
  49. ll pos=lower_bound(pack1[days].begin(),pack1[days].end(),v)-pack1[days].begin();
  50. if(pos==pack1[days].size())
  51. continue;
  52. cost+=pack2[days][pos];
  53. ans=min(ans,cost);
  54. }
  55. if(ans==1e18)
  56. cout<<-1;
  57. else
  58. cout<<ans;
  59. }
Success #stdin #stdout 0s 15240KB
stdin
4 5
1 3 4
1 2 5
5 6 1
1 2 4
stdout
5