Submission #2609689

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef  long long ll;
typedef unsigned long long ull;
const int inf_int=1e8;
const ll inf_ll=1e16;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double dbl;
#define pb push_back
const double pi=3.1415926535898;
#define dout if(debug) cout
#define fi first
#define se second
#define sp setprecision
#define sz(a) (int(a.size()))
#define all(a) a.begin(),a.end()
bool debug = 0;

const int MAXN = 3e5+10;
const int LOG = 20;
const int mod =998244353;



int L[MAXN],R[MAXN];
ll get(int n){
    dout <<"start "<<endl;
    set<pii> l;
    set<pii> r;
    for(int i=1;i<=n;++i){
        r.insert({R[i],i});
        l.insert({L[i],i});
    }

    int cur  =0;
    ll ans =0;
    for(int i=1;i<=n;++i){
        int nxt = -1;
        if(i&1){
            nxt = l.rbegin()->se;
            if(L[nxt] < cur){
                break;
            }
            ans+=abs(L[nxt] - cur);
            cur = L[nxt];
        } else{
            nxt = r.begin()->se;
            if(R[nxt]>cur)
                break;
            ans+=abs(R[nxt] - cur);
            cur = R[nxt];
        }
      //  cout << cur<<" "<<ans<<endl;
        l.erase({L[nxt],nxt});
        r.erase({R[nxt],nxt});
    }
    ans+=abs(cur);
    dout <<"ans "<<ans<<endl;
    return ans;

}
void solve(){
    int n;
    cin >> n;
    for(int i=1;i<=n;++i){
        cin >> L[i] >> R[i];
    }
    ll ans = get(n);
    for(int i=1;i<=n;++i){
        L[i]=-L[i];
        R[i]=-R[i];
        if(L[i]>R[i])
            swap(L[i],R[i]);
    }
    ans = max(ans, get(n));

    cout << ans<<"\n";


}

signed main()
{
        #ifdef taow
           freopen("input.txt","r",stdin);
         //   freopen("output.txt","w",stdout);
        #else
        #endif // taow
        ios_base::sync_with_stdio(0);
        cin.tie(0); cout.tie(0);
        cout.setf(ios::fixed);
        cout.precision(20);



        int t = 1;
        while(t--)
            solve();
}

Submission Info

Judge Result