Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.2 kB
2
Indexable
Never
#include <bits/stdc++.h>

using namespace std;

long long int n, t, ans, l, r, timer, poz_s, max_, sum[1000005], dif, i, j, poz_f;
vector<pair<long long int, long long int> > v;

bool cmp(pair<long long int, long long int> x, pair<long long int, long long int> y){
    return (x.second<y.second) || (x.second==y.second && x.first<y.first);
}

int bs(int st, int dr){
    int ans=0;
    while(st<=dr){
        int mij=(st+dr)/2;
        if(sum[mij]-sum[i]<=t){
            ans=mij;
            st=mij+1;
        }
        else{
            dr=mij-1;
        }
    }
    return ans;
}
void solve(){
    cin>>n>>t;
    for(int i=0; i<n; i++){
        cin>>l>>r;
        v.push_back({l, r});
    }
    
    sort(v.begin(), v.end(), cmp);
    for(i=0; i<v.size(); i++){
       dif=v[i+1].first-v[i].second;
       if(dif<0){
           dif=0;
       }
       sum[i]=sum[i-1]+dif;
    }
    for(i=0; i<v.size(); i++){
        j=bs(i, n-1);
        poz_s=v[i].first;
        poz_f=v[j].second+(t-(sum[j]-sum[i]));
        max_=max(poz_f-poz_s, max_);
    }
    cout<<max_;
    
}

int main(){
  
  solve();

    return 0;
}