ROBOT TS10 PTNK 2018-2019

#define task "ROBOT"

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 1e5 + 5;
constexpr int Inf = 1e9 + 7;
int n, l, r, a[N], b[N];
vector<int> cnt, s;

void Read()
{
    cin >> n >> l >> r;

    // Các vị trí quan trọng cần quan tâm
    s.emplace_back(l);
    s.emplace_back(r);

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i] >> b[i];

        // Các vị trí quan trọng cần quan tâm
        s.emplace_back(a[i]);
        s.emplace_back(b[i]);
    }
}

#define Find(x, v) (lower_bound(x.begin(), x.end(), v) - x.begin() + 1)

void Solve()
{
    // Loại phần tử trùng
    sort(s.begin(), s.end());
    s.resize(unique(s.begin(), s.end()) - s.begin());

    // Khởi tạo mảng cnt[]
    cnt.resize(s.size() + 3, 0);

    for (int i = 1; i <= n; ++i)
    {
        ++cnt[Find(s, a[i])];
        --cnt[Find(s, b[i])];
    }

    vector<int> one;

    for (int i = 1; i <= (int)s.size(); ++i)
    {
        cnt[i] += cnt[i - 1];

        // Liệt kê các vị trí x mà cnt[x] = 1
        if (cnt[i] == 1)
            one.emplace_back(s[i - 1]);
    }

    int ans(0);

    for (int i = 1; i <= n; ++i)
    {
        int x = max(l, a[i]),
            y = min(r, b[i]);

        // Tìm kiếm nhị phân

        if (lower_bound(one.begin(), one.end(), y) - lower_bound(one.begin(), one.end(), x) <= 0) // Có thể điều robot này đi
            ans = max(ans, b[i] - a[i]);
    }

    cout << ans;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }
    Read();
    Solve();
}