Advertisement
Guest User

Untitled

a guest
Jan 18th, 2019
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.11 KB | None | 0 0
  1.  
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. vector < pair < long long, long long > > v[200100];
  7. vector < pair < long long, long long > >::iterator it;
  8. long long l[200100],r[200100],c[200100];
  9. int main()
  10. {
  11. long long n, x,Answer = 2e18,Min;
  12. cin>>n>>x;
  13. for(int i=0; i<n; i++)
  14. {
  15. cin>>l[i]>>r[i]>>c[i];
  16. v[(r[i]-l[i]+1)].push_back(make_pair(l[i],c[i]));
  17. }
  18. for(int i=1; i<=2e5; i++)
  19. {
  20. Min = 1e18;
  21. if(v[i].size()>=2)
  22. {
  23. sort(v[i].begin(),v[i].end());
  24. for(int j=v[i].size()-1; j>=0; j--)
  25. {
  26. v[i][j].second = min(v[i][j].second,Min);
  27. Min=min(Min,v[i][j].second);
  28. }
  29. }
  30. }
  31. for(int i=0; i<n; i++)
  32. {
  33. if(x-(r[i]-l[i]+1) <= 0) continue;
  34. it = upper_bound(v[x-(r[i]-l[i]+1)].begin(),v[x-(r[i]-l[i]+1)].end(),pair < long long, long long >(r[i],-1));
  35. if(it==v[x-(r[i]-l[i]+1)].end()) continue;
  36. else Answer = min(Answer, c[i] + it->second);
  37. }
  38. Answer == 2e18 ? cout<<"-1" : cout<<Answer;
  39. return 0;
  40. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement