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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct Przedzial{
    long long l;
    long long r;
}przedzial;

bool porownaj(const Przedzial &a, const Przedzial &b){
    return a.l < b.l;
}

long long n, szkola;
int m;
bool debug = false;

int main(){
    vector<Przedzial> zajete, wolne;
    scanf(" %lld %d %lld",&n, &m, &szkola);
    for(int i=0; i<m; i++){
        scanf("%lld %lld", &przedzial.l, &przedzial.r);
        zajete.push_back( przedzial );
    }
    //posortuj przedzialy ciagow zajetych budynkow w kolejnosci rosnacej
    sort(zajete.begin(),zajete.end(),porownaj);

    if(debug)
        for(int i=0; i<zajete.size(); i++){
            printf("%lld %lld\n", zajete[i].l, zajete[i].r);
        }
    //na bazie tych przedzialow utworz przedzialy budynkow wolnych

    //sprawdz czy na poczatku miasta sa juz wolne mieszkania
    if(zajete[0].l > 1){
        przedzial.l = 1;
        przedzial.r = zajete[0].l-1;
        wolne.push_back( przedzial );
    }
    //nastepnie utworz przedzialy na zasadzie inwersji
    for(int i=1; i<zajete.size(); i++){
        if(zajete[i-1].r+1 != zajete[i].l){
            przedzial.l = zajete[i-1].r+1;
            przedzial.r = zajete[i].l-1;
            wolne.push_back( przedzial );
        }
    }
    //zobacz tez czy nie oznaczyc tak samo wolnych mieszkan na koncu miasta
    int nZ = zajete.size() - 1;
    if(zajete[ nZ ].r < n){
        przedzial.l = zajete[ nZ ].r + 1;
        przedzial.r = n;
        wolne.push_back( przedzial );
    }
    //czy szkola znajduje sie w ciagu poczatkowych lub koncowych zamieszkanych budynkow
    //wskaz najblizszy pusty dom
    int nW = wolne.size() - 1;
    if(wolne[0].l > szkola){
        printf("%lld\n",wolne[0].l);
        return 0;
    }
    if(wolne[ nW ].r < szkola){
        printf("%lld\n",wolne[nW].r);
        return 0;
    }

    if(debug) printf("\nWolne:\n");
    for(int i=1; i<wolne.size(); i++){
        if(debug) printf("%lld %lld\n", wolne[i].l, wolne[i].r);
        if( wolne[i].l > szkola){
            if( wolne[i].l - szkola >= szkola - wolne[i-1].r )
                printf("%lld\n",wolne[i-1].r);
            else
                printf("%lld\n",wolne[i].l);
            return 0;
        }
    }
    return 0;
}