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

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

    vector<pair<long long, long long>> locked(m);
    for (int i = 0; i < m; i++){
        cin >> locked[i].first >> locked[i].second;
    }

    sort(locked.begin(), locked.end());
    vector<pair<long long, long long>> merged;

    for (int i = 0; i < m; i++){
        long long l = locked[i].first, r = locked[i].second;
        if (!merged.empty() && merged.back().second + 1 >= l){
            merged.back().second = max(merged.back().second, r);
        } else {
            merged.push_back({l, r});
        }
    }

    long long closest = -1;
    long long min_dist = LLONG_MAX;

    if (merged[0].first > 1){
        long long cand = merged[0].first - 1;
        long long dist = abs(s - cand);
        if (dist < min_dist || (dist == min_dist && cand < closest)){
            min_dist = dist;
            closest = cand;
        }
    }

    for (size_t i = 0; i < merged.size() - 1; i++){
        if (merged[i].second + 1 < merged[i + 1].first){
            long long cand1 = merged[i].second + 1;
            long long cand2 = merged[i + 1].first - 1;
            long long dist1 = abs(s - cand1);
            long long dist2 = abs(s - cand2);

            if (dist1 < min_dist || (dist1 == min_dist && cand1 < closest)){
                min_dist = dist1;
                closest = cand1;
            }
            if (dist2 < min_dist || (dist2 == min_dist && cand2 < closest)){
                min_dist = dist2;
                closest = cand2;
            }
        }
    }

    if (merged.back().second < n){
        long long cand = merged.back().second + 1;
        long long dist = abs(s - cand);
        if (dist < min_dist || (dist == min_dist && cand < closest)){
            min_dist = dist;
            closest = cand;
        }
    }

    cout << closest << "\n";
}