fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define pb push_back
  5. #define sz(a) a.size()
  6. #define endl '\n'
  7. #define inf int(1e10)
  8. #define mod inf+7
  9. #define fast_io() std::ios::sync_with_stdio(0)
  10. #define rep(i,a,b) for( int i=a; i<b; i++)
  11.  
  12. using namespace std;
  13.  
  14.  struct voucher{
  15.   int l;
  16.   int r;
  17.   int cost;
  18.   int dur;
  19.  };
  20.  
  21. bool comp(voucher a, voucher b)
  22.   {
  23.     if ( (a.dur)<(b.dur))
  24.       return 1;
  25.     else if (a.dur==b.dur)
  26.       return a.cost<=b.cost;
  27.     else
  28.       return 0;
  29.   }
  30.   int main()
  31.    {
  32.     int n,x;
  33.     voucher t[200005];//TO CHANGE LATER
  34.     cin>>n>>x;
  35.     for(int i=0;i<n;i++)
  36.       {
  37.         cin>>t[i].l>>t[i].r>>t[i].cost;
  38.         t[i].dur=t[i].r-t[i].l+1;
  39.       }
  40.  
  41.    sort(t,t+n,comp);
  42.  
  43.    int i=0; int j=n-1;
  44.    int ans=inf;
  45.    while(i<j)
  46.    {
  47.      if (t[i].dur+t[j].dur==x)
  48.      {
  49.        if (t[i].r<t[j].l || t[j].r<t[i].l)
  50.          ans=min(ans,t[i].cost+t[j].cost);
  51.  
  52.         i--;
  53.      }
  54.       if (t[i].dur+t[j].dur>x)
  55.         j--;
  56.       if (t[i].dur+t[j].dur<x)
  57.         i++;
  58.    }
  59.  
  60.    if (ans==inf )
  61.     cout<<-1;
  62.    else
  63.     cout<<ans;
  64.    }
  65.  
Success #stdin #stdout 0s 19048KB
comments (?)
stdin
copy 
4 5
1 3 4
1 2 5
5 6 1
1 2 4
stdout
copy 
5
https://ideone.com/avXw3e
language:
C++ (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!