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
#include <bits/stdc++.h>
using namespace std;
#define int long
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    long long n; int m, k;
    cin >> n >> m >> k;
    vector<pair<long long, long long>> t(m);
    for (auto& [x, y]: t) cin >> x >> y;

    sort(t.begin(), t.end());
    // join
    vector<pair<int, int>> comp;
    int l = -1, r = -1;
    for (int i=0; i<m; i++) {
//        cout << "idx " << i << ":" <<  l << " " << r << "\n";
        if (l == -1) {
            l = t[i].first;
            r = t[i].second;
            continue;
        }
        if (t[i].first-1 == r) {
            r = t[i].second;
            continue;
        }
        comp.emplace_back(l, r);
        l = t[i].first, r = t[i].second;
    }
    if (l != -1) {
        comp.emplace_back(l, r);
    }

    //vector<pair<int, int>> empt;
    //if (comp[0].first != 1) empt.push_back({1, comp[0].first-1});
    //int s = comp.size();
    //for (int i=1; i<s; i++)
        //empt.push_back({comp[i-1].second+1, comp[i].first-1});
    //if (comp[s-1].second != n) empt.push_back({comp[s-1].second+1, n});

//    for (auto [x, y]: comp) cout << "c: " << x << " " << y << "\n";

    int res = INT_MAX;
    // binsearch for a range in comp that has k in it
    for (auto [x, y]: comp) {
        if (!(x <= k && k <= y)) continue;
        if (x != 1) res = x-1;
        if (y != n)
          if (abs(k-res) > abs(y+1-k))
            res = y+1;
        break;
    }

//    int res = INT_MAX;
//    int e = empt.size();
//    cout << "----\n";
//    for (auto& [x, y]: comp) cout << x << " " << y << "\n";
//    cout << "----\n";
//    for (auto& [x, y]: empt) cout << x << " " << y << "\n";
//    for (int i=0; i<e; i++) {
//        if (empt[i].first < k && k < empt[i].second) {
//            res = i-1;
//            break;
//        }
//        if (empt[i].first == k && empt[i].first != empt[i].second) {
//            res = k+1;
//            break;
//        }
//        if (empt[i].second == k && empt[i].first != empt[i].second) {
//            res = k-1;
//            break;
//        }
//        if (empt[i].second < k) {
//            res = empt[i].second;
//            if (abs(res-k) == 1) break;
//        }
//        if (empt[i].first > k)
//            if (abs(k-empt[i].first) < abs(k-res)) {
//                res = empt[i].first;
//            }
//    }
    cout << res << "\n";
}