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
116
117
118
119
#include <iostream>
#include <vector>

using namespace std;

void mergeSort(vector<vector<long long>>& intervals, long long left, long long right) {
    if (left < right) {
        long long mid = left + (right - left) / 2;

        mergeSort(intervals, left, mid);
        mergeSort(intervals, mid + 1, right);

        vector<vector<long long>> temp;
        long long i = left, j = mid + 1;

        while (i <= mid && j <= right) {
            if (intervals[0][i] <= intervals[1][j]) {
                temp.push_back({intervals[0][i], intervals[1][i]});
                i++;
            } else {
                temp.push_back({intervals[0][j], intervals[1][j]});
                j++;
            }
        }
        while (i <= mid) {
            temp.push_back({intervals[0][i], intervals[1][i]});
            i++;
        }

        while (j <= right) {
            temp.push_back({intervals[0][j], intervals[1][j]});
            j++;
        }
        for (long long k = 0; k < temp.size(); k++) {
            intervals[0][left + k] = temp[k][0];
            intervals[1][left + k] = temp[k][1];
        }
    }
}

int main() {
    ios::sync_with_stdio(0);

    long long n, m, s;
    long long tmpi, tmpj;

    cin>>n>>m>>s;
    vector<vector<long long>> intervals(2, vector<long long>(m));
    for (long long i=0; i<m; i++) {
        cin>>tmpi>>tmpj;
        intervals[0][i] = tmpi;
        intervals[1][i] = tmpj;
    }
    mergeSort(intervals, 0, m - 1);

    long long left = 0;
    long long right = m;
    long long pivot = m/2;
    bool jeszcze = true;
    while (jeszcze) {
        if (intervals[0][pivot] <= s && intervals[1][pivot] >= s) {
            jeszcze = false;
        } else if (intervals[0][pivot] > s) {
            right = pivot;
            pivot = (left + right) /2;
        } else if (intervals[1][pivot] < s) {
            left = pivot;
            pivot = (left + right) /2;
        }
    }
    jeszcze = true;
    long long result = -1;
    for (long long i=pivot; i>0 && jeszcze; i--) {
        if (intervals[1][i-1] < intervals[0][i] - 1) {
            jeszcze = false;
            result = intervals[0][i] - 1;
        }
    }

    if (result == -1 && intervals[0][0] != 1) {
        result = intervals[0][0] - 1;
    }
    jeszcze = true;
    long long result2 = -1;
    for (long long i=pivot; i<m-1 && jeszcze; i++) {
        if (intervals[1][i] < intervals[0][i+1] - 1) {
            jeszcze = false;
            result2 = intervals[1][i] + 1;
        }
    }
    if (result2 == -1 && intervals[1][m-1] != n) {
        result2 = intervals[1][m-1] + 1;
    }

    if (result == -1) {
        cout << result2;
        return 0;
    }
    if (result2 == -1) {
        cout << result;
        return 0;
    }

    long long result11 = s - result < 0 ? result - s : s - result;
    long long result22 = s - result2 < 0 ? result2 - s : s - result2;
    if (result11 == result22) {
        if (result < result2) {
            cout << result;
        } else {
            cout<< result2;
        }
    }else if (result11 < result22) {
        cout << result;
    } else {
        cout << result2;
    }

    return 0;
}