fork download
copy 
  1. //Hacker, pack your bags!
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5. vector < pair < pair<ll,ll>,ll> > v[2*123456];
  6. vector < pair< pair <ll,ll>,ll> > v2[2*123456];
  7.  
  8. int main()
  9. {
  10. 	ll i,j;
  11. 	ll N,X;
  12. 	scanf("%lld%lld",&N,&X);
  13. 	for(i=0;i<N;i++)
  14. 	{
  15. 		ll L,R,C;
  16. 		scanf("%lld%lld%lld",&L,&R,&C);
  17. 		v[R-L+1].push_back(make_pair(make_pair(L,R),C));
  18. 		v2[R-L+1].push_back(make_pair(make_pair(L,R),C));	
  19. 	}	
  20. 	for(i=1;i<=X;i++)
  21. 	{
  22. 	       if((ll)v[i].size()>0)
  23. 	       {
  24. 	              ll temp=1e18;
  25.        		sort(v[i].begin(),v[i].end());
  26.        		for(j=v[i].size()-1;j>=0;j--)
  27.        		{
  28.        			temp=min(temp,v[i][j].second);
  29.        			v[i][j].second=temp;
  30.        		}
  31. 	       }
  32. 	}
  33. 	ll ans=1e18;
  34. 	for(i=1;i<=X;i++)
  35. 	{
  36. 	       if((ll)v2[i].size()>0 &&(ll)v[X-i].size()>0)
  37. 	       {
  38.  
  39.        		for(j=0;j<v2[i].size();j++)
  40.        		{
  41.        			ll K=v2[i][j].first.second;
  42.        			ll L=0;
  43.        			ll R=v[X-i].size()-1;
  44.        			ll pos=-1;
  45.        			if(K>v[X-i][R].first.first)
  46.        			continue;
  47.        			while(L<=R)//just greater
  48.        			{
  49.        				ll mid=(L+R)/2;
  50.        				if(v[X-i][mid].first.first>K)
  51.        				{
  52.        					pos=mid;
  53.        					R=mid-1;
  54.        				}
  55.        				else
  56.        				L=mid+1;
  57.        			}
  58.        			ans=min(ans,v[X-i][pos].second+v2[i][j].second);
  59.        		}
  60.  
  61. 	       }
  62. 	}
  63. 	if(ans==1e18)
  64. 	printf("-1");
  65. 	else
  66. 	printf("%lld",ans);
  67. 	return 0;
  68. }
Runtime error #stdin #stdout 0s 26816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jPRj1i
4 5
1 3 4
1 2 5
5 6 1
1 2 4
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!