fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define X first
  4. #define Y second
  5.  
  6. bool compare(const pair<pair<int,int>, int> &a,const pair<pair<int,int>, int> &b)
  7. {
  8.     if(a.X.X != b.X.X)
  9.     return a.X.X < b.X.X;
  10.     else if(a.X.Y != b.X.Y)
  11.     return a.X.Y < b.X.Y;
  12.     else if(a.Y != b.Y)
  13.     return a.Y < b.Y; 
  14. }
  15.  
  16. int main()
  17. {
  18.     int n, x;
  19.  
  20.     cin >> n >> x;
  21.  
  22.     vector<pair<pair<int, int>, int> > v;
  23.  
  24.     int l, r, c;
  25.  
  26.     for(int i = 0; i < n; i++)
  27.     {
  28.         cin >> l >> r >>c;
  29.  
  30.         v.push_back(make_pair(make_pair(l, r), c));
  31.     } 
  32.  
  33.     sort(v.begin(), v.end(), compare);
  34.  
  35.     int ans = INT_MAX;
  36.     for(int i = 0; i < v.size(); i++)
  37.     {
  38.         int low = i + 1, high = v.size() - 1, mid, flag = 0, temp = INT_MAX;
  39.  
  40.         if(max(low, high) >= v.size())
  41.             break;
  42.  
  43.         while(low <= high)
  44.         {
  45.             mid = low + (high - low) / 2;
  46.             if(v[mid].X.X > v[i].X.Y)
  47.             {
  48.                 int t1, t2;
  49.                 t1 = v[i].X.Y - v[i].X.X + 1;
  50.                 t2 = v[mid].X.Y - v[mid].X.X + 1;
  51.                 if(t1 + t2 == x)
  52.                 {
  53.                     flag = 1;
  54.                     temp = min(temp, v[i].Y + v[mid].Y);
  55.                     high = mid - 1;
  56.                 }
  57.                 else if(t1 + t2 < x)
  58.                     low = mid + 1;
  59.                 else high = mid - 1;
  60.             }
  61.             else low = mid + 1;
  62.         }
  63.         if(flag)
  64.         {
  65.             ans = min(ans, temp); 
  66.         }
  67.     }
  68.  
  69.     if(ans == INT_MAX)
  70.         cout << "-1\n";
  71.     else cout << ans <<"\n";
  72.  
  73.     return 0;
  74. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
4 5
1 3 4
1 2 5
5 6 1
1 2 4
stdout
copy 
5
https://ideone.com/hC25Oz
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!