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
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

#define F first
#define S second
#define ull unsigned long long
#define ll long long

using namespace std;

ll znajdzPrzedzialZSzkola(vector<pair<ull, ull>>& przedzialy, ull& s) {
    ull l = 0;
    ull m = 0;
    ull h = przedzialy.size() - 1;

    while (l <= h) {
        m = l + (h - l) / 2;

        if (przedzialy[m].F <= s && przedzialy[m].S >= s) {
            return m;
        }
        else if (przedzialy[m].S < s) {
            l = m + 1;
        }
        else {
            h = m - 1;
        }
    }

    return 0;
}

ull szukajLewo(vector<pair<ull, ull>>& przedzialy, ll i) {
    ull b = 0;

    while (i >= 0 && b == 0) {
        if (przedzialy[i].S + 1 != przedzialy[i + 1].F) {
            return przedzialy[i + 1].F - 1;

        }

        i--;
    }

    if (b == 0 && przedzialy[0].F - 1 >= 0) {
        return przedzialy[0].F - 1;
    }

    return b;
}

ull szukajPrawo(vector<pair<ull, ull>>& przedzialy, ull i, ll budynki) {
    int n = przedzialy.size();
    ull b = 0;

    while (i < n && b == 0) {
        if (przedzialy[i - 1].S + 1 != przedzialy[i].F) {
            return przedzialy[i - 1].S + 1;
        }

        i++;
    }

    if (b == 0 && przedzialy[n - 1].S <= budynki) {
        return przedzialy[n - 1].S + 1;
    }

    return b;
}

int main() {
    ull n, m, s;

    cin >> n >> m >> s;

    vector<pair<ull, ull>> przedzialy;

    ull l, r;

    for (int i = 0; i < m; i++) {
        cin >> l >> r;
        przedzialy.push_back({ l, r });
    }

    sort(begin(przedzialy), end(przedzialy));


    ll przedzialSzkoly = znajdzPrzedzialZSzkola(przedzialy, s);


    ull lewo = 0;
    ull prawo = 0;


    lewo = szukajLewo(przedzialy, przedzialSzkoly - 1);
    prawo = szukajPrawo(przedzialy, przedzialSzkoly + 1, n);

    if (lewo == 0) {
        cout << prawo;
    }
    else if (prawo == 0) {
        cout << lewo;
    }
    else if (s - lewo > prawo - s) {
        cout << prawo;
    }
    else {
        cout << lewo;
    }


    return 0;
}