Submission #8275518

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define debug(x) cerr<<#x<<": "<<x<<endl
#define trav(a,x) for(auto &a:x)
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> l(n), r(n);
    rep(i,0,n) cin >> l[i] >> r[i];
    int j=0, k=0;
    rep(i,1,n) {
        if(l[i]>l[j]) j = i;
        if(r[i]<r[k]) k = i;
    }
    ll left = max(l[j], l[k]), right = min(r[j],r[k]);
    ll widest = 0;
    rep(i,0,n) widest=max(widest,r[i]-l[i]+1);
    ll ans = max(0LL,right-left+1)+widest;
    if(j!=k) {
        vector<pair<ll,ll>> v;
        rep(i,0,n) if(i!=j && i!=k) {
            v.emplace_back(max(0LL,r[k]-l[i]+1),max(0LL,r[i]-l[j]+1));
        }
        sort(all(v));
        ll ba = r[k]-l[k]+1, bb = r[j]-l[j]+1;
        ll best=0;
        rep(i,0,n-1) {
            ll a = ba;
            if(i<n-2) a = min(a, v[i].first);
            if(i-1>=0) bb = min(bb, v[i-1].second);
            best=max(best,a+bb);
        }
        ans = max(ans,best);
    }
    cout<<ans<<endl;
}

Submission Info

Judge Result