#include <algorithm> #include <iostream> #include <vector> using namespace std; struct Interval { long long l, r; }; int main() { long long n, m, s; cin >> n >> m >> s; vector<Interval> intervals(m); // Wczytanie przedziałów for (int i = 0; i < m; i++) { cin >> intervals[i].l >> intervals[i].r; } // Sortowanie przedziałów według wartości początkowej l sort(intervals.begin(), intervals.end(), [](const Interval &a, const Interval &b) { return a.l < b.l; }); // Przeszukujemy wokół s, aby znaleźć pierwszy wolny budynek size_t i = 0; while (i < intervals.size() && intervals[i].r < s) i++; int start_interval = i; // Najpierw szukamy w lewo int left_i = i, right_i = i; long long left = 0; while (left_i >= 1 && intervals[left_i].l == intervals[left_i - 1].r + 1) { left_i--; } left = intervals[left_i].l - 1; // Szukamy w prawo long long right = n; while (right_i < m && intervals[right_i].r == intervals[right_i + 1].l - 1) { right_i++; } right = intervals[right_i].r + 1; // Porównanie, który budynek jest bliżej long long best_building = -1; if (left >= 1 && (right > n || abs(s - left) <= abs(s - right))) { best_building = left; } else if (right <= n) { best_building = right; } cout << best_building << 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 | #include <algorithm> #include <iostream> #include <vector> using namespace std; struct Interval { long long l, r; }; int main() { long long n, m, s; cin >> n >> m >> s; vector<Interval> intervals(m); // Wczytanie przedziałów for (int i = 0; i < m; i++) { cin >> intervals[i].l >> intervals[i].r; } // Sortowanie przedziałów według wartości początkowej l sort(intervals.begin(), intervals.end(), [](const Interval &a, const Interval &b) { return a.l < b.l; }); // Przeszukujemy wokół s, aby znaleźć pierwszy wolny budynek size_t i = 0; while (i < intervals.size() && intervals[i].r < s) i++; int start_interval = i; // Najpierw szukamy w lewo int left_i = i, right_i = i; long long left = 0; while (left_i >= 1 && intervals[left_i].l == intervals[left_i - 1].r + 1) { left_i--; } left = intervals[left_i].l - 1; // Szukamy w prawo long long right = n; while (right_i < m && intervals[right_i].r == intervals[right_i + 1].l - 1) { right_i++; } right = intervals[right_i].r + 1; // Porównanie, który budynek jest bliżej long long best_building = -1; if (left >= 1 && (right > n || abs(s - left) <= abs(s - right))) { best_building = left; } else if (right <= n) { best_building = right; } cout << best_building << endl; return 0; } |