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
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>

#ifdef DEBUG
#define debug constexpr(true)
#else
#define debug constexpr(false)
#endif

using u64 = std::uint64_t;

u64 n, m, s;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  std::cin >> n >> m >> s;

  struct range {
    u64 a, b;

    bool contains(u64 x) const { return a <= x && x <= b; }
  };

  std::vector<range> ranges;
  for (u64 i = 0; i < m; ++i) {
    u64 a, b;
    std::cin >> a >> b;
    ranges.push_back(range{.a = a, .b = b});
  }

  std::ranges::sort(ranges, [](range const &a, range const &b) {
    assert(a.a != b.a);
    return a.a < b.a;
  });

  // for (u64 i = 0; i < m; ++i)
  //   std::cerr << "[" << ranges[i].a << ", " << ranges[i].b << "]\n";

  for (u64 i = 0; i < m; ++i) {
    range rg = ranges[i];
    if (rg.contains(s)) {
      u64 ld = UINT64_MAX;
      u64 lr = UINT64_MAX;
      u64 rd = UINT64_MAX;
      u64 rr = UINT64_MAX;

      u64 li = i;
      for (;;) {
        u64 nli = li - 1;
        if (li != 0 && ranges[li].a == ranges[nli].b + 1)
          li = nli;
        else {
          ld = s - ranges[li].a;
          lr = ranges[li].a - 1;
          break;
        }
      }

      if (lr == 0)
        ld = UINT64_MAX;

      u64 ri = i;
      for (;;) {
        u64 nri = ri + 1;
        if (nri != m && ranges[ri].b == ranges[nri].a - 1)
          ri = nri;
        else {
          rd = ranges[ri].b - s;
          rr = ranges[ri].b + 1;
          break;
        }
      }

      if (rr == n + 1)
        rd = UINT64_MAX;

      // std::cerr << ld << ' ' << lr << ' ' << rd << ' ' << rr << '\n';

      if (ld <= rd)
        std::cout << lr << '\n';
      else
        std::cout << rr << '\n';

      return 0;
    }
  }

  std::cerr << "school is not occupied?\n";
  return 1;
}