// Catling #include <bits/stdc++.h> using namespace std; #ifdef DEBUG auto operator<<(auto&o,auto p)->decltype(p.first,o){return o<<'('<<p.first<<", "<<p.second <<')';} auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<'{';int i=2;for(auto e:x)o<<(", ")+i<<e,i=0;return o<<'}';} #define LOG(x...)cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(x); #else #define LOG(x...)(void)0 #endif typedef long long ll; typedef pair<ll,ll> pll; typedef pair<int, int> pii; mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); #define all(x) (x).begin(),(x).end() #define endl '\n' #define size(x) x.size() const ll INF = 9223372036854775806; const ll MAX_N = 1e9+1; const ll MOD = 1e9+7; // 998244353 struct Interval { long long l, r; Interval(long long a, long long b) : l(a), r(b) {} }; bool compareIntervals(const Interval &a, const Interval &b) { return a.l < b.l; } void solveTestCase() { long long N, M, S; cin >> N >> M >> S; vector<Interval> intervalsArray; for (int i = 0; i < M; ++i) { long long L, R; cin >> L >> R; intervalsArray.emplace_back(L, R); } sort(intervalsArray.begin(), intervalsArray.end(), compareIntervals); vector<Interval> freeIntervals; if (intervalsArray[0].l > 1) { freeIntervals.emplace_back(1, intervalsArray[0].l - 1); } for (int i = 1; i < size(intervalsArray); ++i) { long long previousInterval = intervalsArray[i-1].r; long long currentInterval = intervalsArray[i].l; if (previousInterval + 1 <= currentInterval - 1) { freeIntervals.emplace_back(previousInterval + 1, currentInterval - 1); } } long long lastR = intervalsArray.back().r; if (lastR < N) { freeIntervals.emplace_back(lastR + 1, N); } long long bestP = -1; long long minDistance = LLONG_MAX; for (const auto &freeInterval : freeIntervals) { long long a = freeInterval.l; long long b = freeInterval.r; long long candidate; if (b < S) { candidate = b; } else if (a > S) { candidate = a; } else { continue; } long long distanceValue = abs(S - candidate); if (distanceValue < minDistance || (distanceValue == minDistance && candidate < bestP)) { minDistance = distanceValue; bestP = candidate; } } cout << bestP << endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int T = 1; while(T--) { solveTestCase(); } return 0; }
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 96 97 98 99 100 | // Catling #include <bits/stdc++.h> using namespace std; #ifdef DEBUG auto operator<<(auto&o,auto p)->decltype(p.first,o){return o<<'('<<p.first<<", "<<p.second <<')';} auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<'{';int i=2;for(auto e:x)o<<(", ")+i<<e,i=0;return o<<'}';} #define LOG(x...)cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(x); #else #define LOG(x...)(void)0 #endif typedef long long ll; typedef pair<ll,ll> pll; typedef pair<int, int> pii; mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); #define all(x) (x).begin(),(x).end() #define endl '\n' #define size(x) x.size() const ll INF = 9223372036854775806; const ll MAX_N = 1e9+1; const ll MOD = 1e9+7; // 998244353 struct Interval { long long l, r; Interval(long long a, long long b) : l(a), r(b) {} }; bool compareIntervals(const Interval &a, const Interval &b) { return a.l < b.l; } void solveTestCase() { long long N, M, S; cin >> N >> M >> S; vector<Interval> intervalsArray; for (int i = 0; i < M; ++i) { long long L, R; cin >> L >> R; intervalsArray.emplace_back(L, R); } sort(intervalsArray.begin(), intervalsArray.end(), compareIntervals); vector<Interval> freeIntervals; if (intervalsArray[0].l > 1) { freeIntervals.emplace_back(1, intervalsArray[0].l - 1); } for (int i = 1; i < size(intervalsArray); ++i) { long long previousInterval = intervalsArray[i-1].r; long long currentInterval = intervalsArray[i].l; if (previousInterval + 1 <= currentInterval - 1) { freeIntervals.emplace_back(previousInterval + 1, currentInterval - 1); } } long long lastR = intervalsArray.back().r; if (lastR < N) { freeIntervals.emplace_back(lastR + 1, N); } long long bestP = -1; long long minDistance = LLONG_MAX; for (const auto &freeInterval : freeIntervals) { long long a = freeInterval.l; long long b = freeInterval.r; long long candidate; if (b < S) { candidate = b; } else if (a > S) { candidate = a; } else { continue; } long long distanceValue = abs(S - candidate); if (distanceValue < minDistance || (distanceValue == minDistance && candidate < bestP)) { minDistance = distanceValue; bestP = candidate; } } cout << bestP << endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int T = 1; while(T--) { solveTestCase(); } return 0; } |