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

using namespace std;

struct Przedzial {
    long long start, end;
};

bool comp(Przedzial a, Przedzial b) {
    return a.start < b.start;
}

void dodaj(long long start, long long end, vector<Przedzial> *wolne) {
    if (start > end) return;
    Przedzial p;
    p.start = start;
    p.end = end;
    wolne->push_back(p);
}

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

    vector<Przedzial> zajete;
    vector<Przedzial> wolne;

    scanf("%lld %lld %lld", &n, &m, &s);

    for (int i = 0; i < m; i++) {
        long long l, r;
        scanf("%lld %lld", &l, &r);
        Przedzial p;
        p.start = l;
        p.end = r;
        zajete.push_back(p);
    }

    sort(zajete.begin(), zajete.end(), comp);

    dodaj(1L, zajete[0].start - 1, &wolne);
    for (int i = 0; i < m - 1; i++) {
        dodaj(zajete[i].end + 1, zajete[i + 1].start - 1, &wolne);
    }
    dodaj(zajete[m - 1].end + 1, n, &wolne);

    /*
    for (auto it = zajete.begin(); it != zajete.end(); it++) {
        printf("%lld %lld\n", it->start, it->end);
    }

    for (auto it = wolne.begin(); it != wolne.end(); it++) {
        printf("%lld %lld\n", it->start, it->end);
    }
    */

    bool findLeft = false;
    bool findRight = false;
    long long left, right;

    for (auto it = wolne.begin(); it != wolne.end(); it++) {
        if (it->end < s) {
            left = it->end;
            findLeft = true;
        }
        if (!findRight && it->start > s) {
            right = it->start;
            findRight = true;
        }
    }

    if (findLeft && !findRight) {
        printf("%lld", left);
    }

    if (!findLeft && findRight) {
        printf("%lld", right);
    }

    if (findLeft && findRight) {
        long lDist = abs(s - left);
        long rDist = abs(s - right);

        if (lDist <= rDist) {
            printf("%lld", left);
        }
        else {
            printf("%lld", right);
        }
    }

    return 0;
}