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
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    long long tancowala, ryba, rak;
    cin >> tancowala >> ryba >> rak;
    
    vector<pair<long long, long long>> pietruszka;
    for (int pasternak = 0; pasternak < ryba; ++pasternak) {
        long long dzwieczyna, kozak;
        cin >> dzwieczyna >> kozak;
        pietruszka.emplace_back(dzwieczyna, kozak);
    }
    
    sort(pietruszka.begin(), pietruszka.end());
    
    int pozycja = -1;
    int lewo = 0, prawo = ryba - 1;
    while (lewo <= prawo) {
        int srodek = (lewo + prawo) / 2;
        if (pietruszka[srodek].first <= rak && rak <= pietruszka[srodek].second) {
            pozycja = srodek;
            break;
        } else if (pietruszka[srodek].first > rak) {
            prawo = srodek - 1;
        } else {
            lewo = srodek + 1;
        }
    }
    
    if (pozycja == -1) {
        return 1;
    }
    
    vector<pair<long long, long long>> dziury;
    long long poprzedni_koniec = 0;
    for (const auto& grzadka : pietruszka) {
        long long dzwieczyna = grzadka.first;
        long long kozak = grzadka.second;
        if (poprzedni_koniec + 1 <= dzwieczyna - 1) {
            dziury.emplace_back(poprzedni_koniec + 1, dzwieczyna - 1);
        }
        poprzedni_koniec = kozak;
    }
    if (poprzedni_koniec < tancowala) {
        dziury.emplace_back(poprzedni_koniec + 1, tancowala);
    }
    
    long long poczatek = pietruszka[pozycja].first;
    long long koniec = pietruszka[pozycja].second;
    long long najlepsza_pozycja = -1;
    long long najlepszy_dystans = LLONG_MAX;
    
    for (const auto& dziura : dziury) {
        long long dzwieczyna = dziura.first;
        long long kozak = dziura.second;
        if (kozak < poczatek) {
            long long kandydat = kozak;
            long long dystans = rak - kandydat;
            if (dystans < najlepszy_dystans || (dystans == najlepszy_dystans && kandydat < najlepsza_pozycja)) {
                najlepszy_dystans = dystans;
                najlepsza_pozycja = kandydat;
            }
        } else if (dzwieczyna > koniec) {
            long long kandydat = dzwieczyna;
            long long dystans = kandydat - rak;
            if (dystans < najlepszy_dystans || (dystans == najlepszy_dystans && kandydat < najlepsza_pozycja)) {
                najlepszy_dystans = dystans;
                najlepsza_pozycja = kandydat;
            }
        }
    }
  
    cout << najlepsza_pozycja << endl;
    
    return 0;
}