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
// PA2025 runda 2C - https://sio2.mimuw.edu.pl/c/pa-2025-1/p/szk/
//-std=c++20
#include<iostream>
#include <algorithm>
#include <vector>
#include<cstdlib>

using namespace std;

u_int64_t n;
u_int16_t m;
u_int64_t s;

struct range_t {
    u_int64_t a, b;
};
vector<range_t> r;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> s;
    r.resize(m);
    for (int i = 0; i < m; ++i) {
        cin >> r[i].a >> r[i].b;
    }
    sort(r.begin(), r.end(), [](const range_t &x, const range_t &y) {
        return x.a < y.a;
    });
    u_int16_t is = m - 1;
    while (r[is].a > s)
        is--;
    //search right
    int32_t ris = is;
    u_int64_t r_found = 0;
    do {
        u_int64_t r_bound;
        if (ris == m - 1) {
            r_bound = n + 1;
        } else {
            r_bound = r[ris + 1].a;
        }
        if (r[ris].b + 1 < r_bound) {
            r_found = r[ris].b + 1;
        } else {
            ris++;
        }
    } while (r_found == 0 && ris < m);
    //search left
    int32_t lis = is;
    u_int64_t l_found = 0;
    do {
        u_int64_t l_bound=0;
        if (lis == 0) {
            l_bound = 0;
        } else {
            l_bound = r[lis - 1].b;
        }
        if (r[lis].a - 1 > l_bound) {
            l_found = r[lis].a - 1;
        } else {
            lis--;
        }
    } while (l_found == 0 && lis >= 0);
    if (l_found && r_found) {
        if ((r_found - s) < (s - l_found)) {
            cout << r_found;
        } else {
            cout << l_found;
        }
    } else if (l_found) {
        cout << l_found;
    } else {
        cout << r_found;
    }
}