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

using namespace std;
using range = pair<unsigned long long, unsigned long long>;

int main() {
  unsigned long long n, m, s;
  vector<range> house_ranges;

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

  for (int i = 0; i < m; i++) {
    range house_range;

    scanf("%llu %llu", &house_range.first, &house_range.second);

    house_ranges.push_back(house_range);
  }

  sort(house_ranges.begin(), house_ranges.end());

  vector<range> merged_ranges;
  range current_range = house_ranges[0];

  for (int i = 1; i < house_ranges.size(); i++) {
    if (current_range.second >= house_ranges[i].first - 1) {
      current_range.second = max(current_range.second, house_ranges[i].second);
    } else {
      merged_ranges.push_back(current_range);
      current_range = house_ranges[i];
    }
  }

  merged_ranges.push_back(current_range);

  for (int i = 0; i < merged_ranges.size(); i++) {
    // printf("%d %d\n", merged_ranges[i].first, merged_ranges[i].second);
    if (merged_ranges[i].first <= s && merged_ranges[i].second >= s) {
      unsigned long long left = s - merged_ranges[i].first;
      unsigned long long right = merged_ranges[i].second - s;

      if (merged_ranges[i].first - 1 <= 0) {
        printf("%llu", merged_ranges[i].second + 1);

        break;
      }

      if (merged_ranges[i].second + 1 > n) {
        printf("%llu", merged_ranges[i].first - 1);

        break;
      }

      if (left <= right) {
        printf("%llu", merged_ranges[i].first - 1);

        break;
      } else {
        printf("%llu", merged_ranges[i].second + 1);

        break;
      }
    }
  }

  return 0;
}