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
#include <bits/stdc++.h>

typedef bool bool_t;
typedef char char_t;
typedef long long int_t;
typedef std::string str_t;

typedef std::pair<int_t, int_t> pairint_t;

typedef std::vector<bool_t> vecbool_t;
typedef std::vector<int_t> vecint_t;
typedef std::vector<pairint_t> vecpairint_t;

int_t n, m, s;
vecpairint_t range;

int_t get_answer(int_t combination);

void s1();

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

    std::cin >> n >> m >> s;

    range.resize(m);

    for(int_t i = 0; i < m; i++)
        std::cin >> range[i].first >> range[i].second;

    s1();

    return 0;
}

void s1()
{
    vecpairint_t range_compressed;
    range_compressed.reserve(m + 1);
    range_compressed.push_back({-1, -1});

    std::sort(range.begin(), range.end());

    for(int_t i = 0; i < m; i++)
    {
        if(range[i].first - range_compressed.back().second <= 1)
        {
            range_compressed.back().second = std::max(range_compressed.back().second, range[i].second);
            continue;
        }

        range_compressed.push_back(range[i]);
    }

    pairint_t abstract_range = {s, LLONG_MAX};
    pairint_t range_closest = *(std::upper_bound(range_compressed.begin(), range_compressed.end(), abstract_range) - 1);

    int_t left_distance = LLONG_MAX, right_distance = LLONG_MAX;

    if(range_closest.first - 1 >= 1)
        left_distance = s - range_closest.first + 1;

    if(range_closest.second + 1 <= n)
        right_distance = range_closest.second - s + 1;

    if(right_distance < left_distance)
    {
        std::cout << (range_closest.second + 1) << '\n';
        return;
    }

    std::cout << (range_closest.first - 1) << '\n';
}