1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll l_domy, n, szkola;
    cin >> l_domy >> n >> szkola;

    vector<pair<ll, ll>> przedzialy;

    for (ll i = 0; i < n; ++i)
    {
        ll start, end;
        cin >> start >> end;
        przedzialy.emplace_back(start, 1);
        przedzialy.emplace_back(end + 1, -1);
    }

    przedzialy.emplace_back(l_domy + 1, 0);
    sort(przedzialy.begin(), przedzialy.end());

    vector<pair<ll, ll>> domy;
    ll dostepne = 0, prev = 0;

    for (auto &[pos, delta] : przedzialy)
    {
        if (prev < pos)
        {
            if (dostepne == 0)
            {
                ll start = prev;
                ll end = pos - 1;
                start = max(start, 1LL);
                end = min(end, l_domy);
                if (start <= end)
                {
                    domy.emplace_back(start, end);
                }
            }
        }
        dostepne += delta;
        prev = pos;
    }

    auto it = upper_bound(domy.begin(), domy.end(), make_pair(szkola, LLONG_MAX));
    if (it != domy.begin())
    {
        --it;
        if (it->second >= szkola)
        {
            cout << szkola << '\n';
            return 0;
        }
    }

    ll candidate1 = -1, candidate2 = -1;

    int lo = 0, hi = domy.size() - 1;
    while (lo <= hi)
    {
        int mid = (lo + hi) / 2;
        if (domy[mid].second <= szkola)
        {
            candidate1 = domy[mid].second;
            lo = mid + 1;
        }
        else
        {
            hi = mid - 1;
        }
    }

    lo = 0, hi = domy.size() - 1;
    while (lo <= hi)
    {
        int mid = (lo + hi) / 2;
        if (domy[mid].first >= szkola)
        {
            candidate2 = domy[mid].first;
            hi = mid - 1;
        }
        else
        {
            lo = mid + 1;
        }
    }

    ll best = -1;
    if (candidate1 != -1)
    {
        best = candidate1;
    }
    if (candidate2 != -1)
    {
        if (best == -1 || abs(candidate2 - szkola) < abs(best - szkola) || (abs(candidate2 - szkola) == abs(best - szkola) && candidate2 < best))
        {
            best = candidate2;
        }
    }

    cout << best << '\n';
}