#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long int LL; const LL INF = 1000000000000000; LL n, m, s, a, b; LL res = INF, minDist = INF; vector<pair<LL, LL>> occupied; int findSRangeIdx() { for (int i = 0; i < occupied.size(); ++i) { if (occupied[i].first <= s && s <= occupied[i].second) { return i; } } return -1; } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); vector<pair<LL, LL>> occupiedAll; cin >> n >> m >> s; for (int i = 0; i < m; ++i) { cin >> a >> b; occupiedAll.push_back(make_pair(a, b)); } sort(occupiedAll.begin(), occupiedAll.end()); int idx = 0; while (idx < occupiedAll.size()) { pair<LL, LL> curr = occupiedAll[idx]; bool inc = true; while (idx + 1 < occupiedAll.size() && occupiedAll[idx].second + 1 == occupiedAll[idx + 1].first) { curr.second = occupiedAll[idx + 1].second; ++idx; inc = false; } occupied.push_back(curr); if (inc) { ++idx; } } int sRangeIdx = findSRangeIdx(); LL left = occupied[sRangeIdx].first - 1; if (left >= 1) { res = left; minDist = s - left; } LL right = occupied[sRangeIdx].second + 1; if (right <= n && right - s < minDist) { res = right; } cout << res << endl; 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 | #include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long int LL; const LL INF = 1000000000000000; LL n, m, s, a, b; LL res = INF, minDist = INF; vector<pair<LL, LL>> occupied; int findSRangeIdx() { for (int i = 0; i < occupied.size(); ++i) { if (occupied[i].first <= s && s <= occupied[i].second) { return i; } } return -1; } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); vector<pair<LL, LL>> occupiedAll; cin >> n >> m >> s; for (int i = 0; i < m; ++i) { cin >> a >> b; occupiedAll.push_back(make_pair(a, b)); } sort(occupiedAll.begin(), occupiedAll.end()); int idx = 0; while (idx < occupiedAll.size()) { pair<LL, LL> curr = occupiedAll[idx]; bool inc = true; while (idx + 1 < occupiedAll.size() && occupiedAll[idx].second + 1 == occupiedAll[idx + 1].first) { curr.second = occupiedAll[idx + 1].second; ++idx; inc = false; } occupied.push_back(curr); if (inc) { ++idx; } } int sRangeIdx = findSRangeIdx(); LL left = occupied[sRangeIdx].first - 1; if (left >= 1) { res = left; minDist = s - left; } LL right = occupied[sRangeIdx].second + 1; if (right <= n && right - s < minDist) { res = right; } cout << res << endl; return 0; } |