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
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;
using ll = long long;

int main() {
    ll n, m, s;
    cin >> n >> m >> s;
    vector<pair<ll, ll>> taken = vector<pair<ll, ll>>(m);

    for (ll i = 0; i < m; i++) {
        cin >> taken[i].first >> taken[i].second;
    }

    sort(taken.begin(), taken.end());

    ll current_strip = m - 1;
    ll best_left = LLONG_MIN + 2000000000000, best_right = LLONG_MAX - 2000000000000;
    ll i = s - 1;

    if (i >= 1) {
        while (current_strip >= 0 && taken[current_strip].first > i) {
            current_strip--;
        }

        while (current_strip >= 0 && taken[current_strip].second >= i) {
            i = taken[current_strip].first - 1;
            current_strip--;
        }
        if (current_strip >= 0 && taken[current_strip].second < i) {
            // found best left
            best_left = i;
        }

        if (best_left == LLONG_MIN + 2000000000000 && taken.front().first > 1) {
            best_left = taken.front().first - 1;
        }
    }

    current_strip = 0;
    i = s + 1;

    if (i <= n) {
        while (current_strip < m && taken[current_strip].second < i) {
            current_strip++;
        }

        while (current_strip < m && taken[current_strip].first <= i) {
            i = taken[current_strip].second + 1;
            current_strip++;
        }
        if (current_strip < m && taken[current_strip].first > i) {
            // found best right
            best_right = i;
        }

        if (best_right == LLONG_MAX - 2000000000000 && taken.back().second < n) {
            best_right = taken.back().second + 1;
        }
    }

    // cout << "best left: " << best_left << ", best right: " << best_right << endl;
    cout << (s - best_left <= best_right - s ? best_left : best_right) << endl;

    return 0;
}