#include <bits/stdc++.h> #include <climits> using namespace std; #define ff first #define ss second #define pb push_back #define eb emplace_back #define FASTIO \ std::ios::sync_with_stdio(false); \ cin.tie(NULL); #ifdef DEBUG #define debug(x) cerr << #x << " = " << x << endl; #else #define debug(x) #endif using ll = long long; using ull = unsigned long long; using vi = vector<int>; using vs = vector<string>; #define ifor(x) for (int i = 0; i < x; i++) #define vcin(v, n) \ ifor(n) { \ int abc; \ cin >> abc; \ v.push_back(abc); \ } void ld(int *container, int n) { for (int i = 0; i < n; i++) { cin >> *(container + i); } } ll odleglosc(ll a, ll b) { return abs(b - a); } int main() { FASTIO ll n, m, s; vector<pair<ll, ll>> prz; cin >> n >> m >> s; prz.reserve(m + 1); for (int i = 0; i < m; i++) { ll li, ri; cin >> li >> ri; prz.pb({li, ri}); } sort(prz.begin(), prz.end()); bool s_nalezy_do_przedzialu = false; for (int i = 0; i < prz.size(); i++) { auto x = prz[i]; if (x.first <= s && x.second >= s) s_nalezy_do_przedzialu = true; } ll min_odleglosc = LLONG_MAX; ll min_dom = LLONG_MAX; if (prz[0].first > 1 && odleglosc(prz[0].first - 1, s) > 0) { min_dom = prz[0].first - 1; min_odleglosc = odleglosc(prz[0].first - 1, s); } if (prz[prz.size() - 1].second < n && odleglosc(prz[prz.size() - 1].second + 1, s) > 0) { if (odleglosc(prz[prz.size() - 1].second + 1, s) < min_odleglosc || (odleglosc(prz[prz.size() - 1].second + 1, s) == min_odleglosc && prz[prz.size() - 1].second < min_dom)) { min_dom = prz[prz.size() - 1].second + 1; min_odleglosc = odleglosc(prz[prz.size() - 1].second + 1, s); } } for (int i = 0; i < prz.size(); i++) { auto x = prz[i]; ll odl_prawo = odleglosc(s, x.second + 1); ll odl_lewo = odleglosc(s, x.first - 1); if (i > 0 && (odl_lewo < min_odleglosc || (odl_lewo == min_odleglosc && x.first - 1 < min_dom)) && odl_lewo != 0) { if (x.first - 1 > prz[i - 1].second) { min_dom = x.first - 1; min_odleglosc = odl_lewo; } } if (i < prz.size() - 1 && (odl_prawo < min_odleglosc || (odl_prawo == min_odleglosc && x.second + 1 < min_dom)) && odl_prawo != 0) { if (x.second + 1 < prz[i + 1].first) { min_dom = x.second + 1; min_odleglosc = odl_prawo; } } } cout << min_dom << "\n"; }
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 | #include <bits/stdc++.h> #include <climits> using namespace std; #define ff first #define ss second #define pb push_back #define eb emplace_back #define FASTIO \ std::ios::sync_with_stdio(false); \ cin.tie(NULL); #ifdef DEBUG #define debug(x) cerr << #x << " = " << x << endl; #else #define debug(x) #endif using ll = long long; using ull = unsigned long long; using vi = vector<int>; using vs = vector<string>; #define ifor(x) for (int i = 0; i < x; i++) #define vcin(v, n) \ ifor(n) { \ int abc; \ cin >> abc; \ v.push_back(abc); \ } void ld(int *container, int n) { for (int i = 0; i < n; i++) { cin >> *(container + i); } } ll odleglosc(ll a, ll b) { return abs(b - a); } int main() { FASTIO ll n, m, s; vector<pair<ll, ll>> prz; cin >> n >> m >> s; prz.reserve(m + 1); for (int i = 0; i < m; i++) { ll li, ri; cin >> li >> ri; prz.pb({li, ri}); } sort(prz.begin(), prz.end()); bool s_nalezy_do_przedzialu = false; for (int i = 0; i < prz.size(); i++) { auto x = prz[i]; if (x.first <= s && x.second >= s) s_nalezy_do_przedzialu = true; } ll min_odleglosc = LLONG_MAX; ll min_dom = LLONG_MAX; if (prz[0].first > 1 && odleglosc(prz[0].first - 1, s) > 0) { min_dom = prz[0].first - 1; min_odleglosc = odleglosc(prz[0].first - 1, s); } if (prz[prz.size() - 1].second < n && odleglosc(prz[prz.size() - 1].second + 1, s) > 0) { if (odleglosc(prz[prz.size() - 1].second + 1, s) < min_odleglosc || (odleglosc(prz[prz.size() - 1].second + 1, s) == min_odleglosc && prz[prz.size() - 1].second < min_dom)) { min_dom = prz[prz.size() - 1].second + 1; min_odleglosc = odleglosc(prz[prz.size() - 1].second + 1, s); } } for (int i = 0; i < prz.size(); i++) { auto x = prz[i]; ll odl_prawo = odleglosc(s, x.second + 1); ll odl_lewo = odleglosc(s, x.first - 1); if (i > 0 && (odl_lewo < min_odleglosc || (odl_lewo == min_odleglosc && x.first - 1 < min_dom)) && odl_lewo != 0) { if (x.first - 1 > prz[i - 1].second) { min_dom = x.first - 1; min_odleglosc = odl_lewo; } } if (i < prz.size() - 1 && (odl_prawo < min_odleglosc || (odl_prawo == min_odleglosc && x.second + 1 < min_dom)) && odl_prawo != 0) { if (x.second + 1 < prz[i + 1].first) { min_dom = x.second + 1; min_odleglosc = odl_prawo; } } } cout << min_dom << "\n"; } |