Ý tưởng:

• Gọi ~A_i~ và ~B_i~ lần lượt là vị trí lấy hàng và vị trí giao hàng của đơn hàng thứ i.
• Trường hợp ~A_i \leq B_i~: Ta không cần quan tâm đến trường hợp này vì cuối cùng ta cũng phải đi đến điểm ~M~ nên trên đường đi từ ~0 \to M~ thì ta luôn luôn có thể lấy hàng từ vị trí ~A_i~ và trả hàng ở vị trí ~B_i~.

• Trường hợp ~A_i \gt B_i~: Ta cần quan tâm đến việc những đơn hàng có giao nhau hay không, tức là chúng có đi qua một số điểm chung hay không. Vì các đơn này đi ngược chiều ban đầu nên kết quả tăng thêm bằng với độ dài ta đi ngược xuống ~B_i~ và lên lại ~A_i~.
  Giả sử ta có ~2~ đơn hàng ~(5,3)~ , ~(4,2)~ và ~M=6~. Ta thấy rằng nếu di chuyển: ~0 \to 4 \to 2 \to 5 \to 3 \to 6~ thì sẽ có những điểm mà đơn hàng ~1~ và ~2~ cùng đi qua. Cách di chuyển: ~0 \to 5 \to 4 \to 2 \to 3 \to 6~ sẽ tối ưu hơn các cách di chuyển khác.

  Giả sử ta có ~2~ đơn hàng ~(6,4)~ và ~(3,2)~ và ~M=7~. Ta thấy cách di chuyển: ~0 \to 3 \to 2 \to 6 \to 4 \to 7~ sẽ là tối ưu.

Cách làm:

• Ta xét các trường hợp đơn hàng có ~A_i \gt B_i~
• Sắp xếp tăng dần theo ~B_i~.
• Nếu đơn hàng tiếp theo giao với tập hợp các đơn hàng hiện tại, ta thêm đơn hàng đó vào tập hợp, nếu không thì tính độ dài của tập hiện tại và đơn hàng tiếp theo sẽ tạo một tập hợp mới.

Code tham khảo

#include<bits/stdc++.h>
#define reu(i,a,b) for(int i=a,_b=b;i<=_b;++i)
#define red(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
#define mp make_pair
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define iii pair<int,pair<int,int> >
#define sz(x) int(x.size())
using namespace std;
//const int N = 3e5 + 7;

ll n, x, y, m, mn, mx, res;
vector< ii > v; // chứa các đơn hàng có A[i]>B[i]

bool cmp(const ii &u, const ii &v)
{
    return( (u.se < v.se) || (u.se == v.se && u.fi > v.fi));
}

void input()
{
    cin >> n >> m;
    reu(i, 1, n)
    {
        cin >> x >> y;
        if(x > y) v.pb({x,y});
    }
    sort(v.begin(), v.end(), cmp);
}

void solve()
{
    res = m; // biến lưu kết quả. Vì trước sau cũng phải đến M nên res = M.
    if(sz(v) == 0)
    {
        cout << m;
        return;
    }
    mn = v[0].se; // vị trí nhỏ nhất của tập hợp hiện tại.
    mx = v[0].fi; // vị trí lớn nhất của tập hợp hiện tại.
    reu(i, 0, sz(v) - 1)
    {
        mx = max(mx, v[i].fi);
        mn = min(mn, v[i].se);
        if( (i == sz(v) - 1) || (mn > v[i+1].fi) || (mx < v[i+1].se)) // nếu đơn hàng tiếp theo không trùng với tập hợp hiện tại hoặc đã xét hết đơn hàng.
        {
            res += (mx - mn) * 2; // độ dài đoạn phải đi ngược xuống và đi lên lại
            if(i == sz(v) - 1) break;
            // Khởi tạo lại tập hợp mới.
            mn = v[i+1].se;
            mx = v[i+1].fi;
        }
    }
    cout << res;
}

int main()
{
    freopen("GIAOHANG.INP","r",stdin);
    freopen("GIAOHANG.OUT","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    input();
    solve();
    return 0;
}