fork download
copy 
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <climits>
  5. struct node{
  6.     int l,r,cost,dur;
  7. };
  8. bool cmp(const node &x, const node &y){
  9.     return x.dur<y.dur;
  10. }
  11. using namespace std;
  12. int main(){
  13.    int n,x;
  14.    scanf("%d %d",&n,&x);
  15.    vector<node> A(n);
  16.    for(int i=0; i<n; ++i){
  17.         int l,r,c;
  18.         scanf("%d %d %d",&l,&r,&c);
  19.         A[i].l=l;
  20.         A[i].r=r;
  21.         A[i].cost=c;
  22.         A[i].dur=r-l+1;  
  23.    }
  24.    sort(A.begin(),A.end(),cmp);
  25.    int ans=INT_MAX;
  26.    for(int i=0; i+1<n; ++i){
  27.        int targ=x-A[i].dur;
  28.        if(targ<1)
  29.             continue;
  30.        int low=i+1,up=n-1;
  31.        while(up>low){
  32.             int mid=(up+low)>>1;
  33.             int dur=A[mid].dur;
  34.             if(dur<targ){
  35.                 if(mid<n)
  36.                     if(A[mid+1].dur=targ){
  37.                         low=mid+1;
  38.                         up=mid+1;
  39.                         break;
  40.                     }
  41.                 low=mid+1;
  42.  
  43.             }
  44.             else
  45.                 up=mid;
  46.         }
  47.        int j=(low+up)>>1; 
  48.        if(j<=i)
  49.             continue;
  50.        int r0=A[i].r, l0=A[i].l;
  51.        int cost0=A[i].cost;
  52.        while(1){
  53.             int dur=A[j].dur;
  54.             if(dur>targ)
  55.                 break;
  56.             int r=A[j].r,l=A[j].l;
  57.             int cost1=A[j].cost+cost0;
  58.             if(cost1<ans)
  59.                 if(r0<l || l0>r)
  60.                     ans=cost1;
  61.             ++j;
  62.             if(j>=n)
  63.                 break;
  64.        }
  65.    }
  66.    if(ans<INT_MAX)
  67.         printf("%d\n",ans);
  68.     else
  69.         printf("-1");
  70.    return 0;
  71. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
3 2
1 1 10
2 2 100
3 3 1000
stdout
copy 
110
https://ideone.com/OHMWiN
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!