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
  #include <iostream>
  #include <stdio.h>
  #include <cstdio>
  #include <vector>
  #include <algorithm>
  using namespace std;

  class Range {
    public:
    long left;
    long right;

    Range(long left, long right) {
      this->left = left;
      this->right = right;
    };
  };

  bool descending(Range& first, Range& second) {
    return first.left > second.left;
  }

  int main() {
    long n;
    int m;
    long s;
    cin >> n >> m >> s;
    
    vector<Range> segments;
    
    for(int i = 0; i < m; i++) {
      long left, right;
      cin >> left >> right;
      segments.emplace_back(Range(left, right));
    }

    sort(segments.begin(), segments.end(), descending);

    vector<Range> merged;
    merged.emplace_back(segments.back());
    segments.pop_back();
    while (segments.size() > 0) {
      auto range = segments.back();
      segments.pop_back();
      if (merged.back().right + 1 == range.left) {
        merged.back().right = range.right;
      } else {
        merged.emplace_back(range);
      }
    }
    
    for (Range range : merged) {
      if(range.left <= s && s <= range.right) {
        long leftCandidate = range.left - 1;
        long rightCandidate = range.right + 1;
        if (leftCandidate < 1) {
          cout << rightCandidate;
        } else if (rightCandidate > n) {
          cout << leftCandidate;
        } else {
          long leftDistance = s - leftCandidate;
          long rightDistance = rightCandidate - s;
          if(rightDistance < leftDistance) {
            cout << rightCandidate;
          } else {
            cout << leftCandidate;
          }
        }
        return 0;
      }
    }

    return -1;
  }