Halny – omówienie zadania

Halny – omówienie zadania

Szczegółowe omówienie zadania Halny:


Link do powyższego omówienia zadania Halny:
https://youtu.be/AWF6rnIKIv8

Link do treści zadania Halny:
https://solve.edu.pl/~sparingi/tasks/view/9

Możliwość umieszczania rozwiązań:
https://solve.edu.pl/~sparingi/tasks


Zadanie Halny wykorzystuje drzewo przedziałowe przedział-punkt.


Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz:
https://youtu.be/pkLXuuOe_qA?t=3625


Kod C++ który jest rozwiązaniem zadania, pochodzi od Darii, uczestniczki Olimpijskiego Koła Informatycznego.
Bardzo dziękuję!


Kod C++ programu Halny, który jest omówiony w powyższym filmie i który otrzymuje 100%


#include <iostream>
#include <algorithm>
 
const int MAX_N = 5e5 + 5;
std::pair<int, int> h[MAX_N], w[MAX_N];
 
const int MAX_PODST = 1<<19;
int drzewo_wysokosci[2*MAX_PODST];
 
void dodaj_drzewo(int index, int wartosc, int podstawa) {
    int v = index + podstawa;
    drzewo_wysokosci[v] = wartosc;
    v /= 2;
    while (v > 0) {
        drzewo_wysokosci[v] = std::max(drzewo_wysokosci[2*v], drzewo_wysokosci[2*v+1]);
        v /= 2;
    }
}
 
int zapytanie_o_prawdziawa_wytrzymalosc(int poczatek, int koniec, int podstawa) {
    int p = poczatek - 1 + podstawa;
    int k = koniec + 1 + podstawa;
    int wynik = 0;
    while (p/2 != k/2) {
        if (p%2 == 0) {
            wynik = (std::max(drzewo_wysokosci[p+1], wynik));
        }
        if (k%2 == 1) {
            wynik = std::max(drzewo_wysokosci[k-1], wynik);
        }
        p /= 2;
        k /= 2;
    }
    return wynik;
}
 
bool wysokosc_maleje_index_rosnie(std::pair<int, int> p1, std::pair<int, int> p2) {
    if (p1.first == p2.first) {
        return p1.second < p2.second;
    }
    return p1.first > p2.first;
}
 
bool index_rosnie(std::pair<int, int> p1, std::pair<int, int> p2) {
    return p1.second < p2.second;
}
 
int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    int n, m;
    int wysokosc, wytrzymalosc, s;
    int podstawa_drzewa_przedzialowego = 1;
    int ostatnie_powalone_drzewo = 1;
    int wynik;
 
    std::cin >> n >> m;
    while (podstawa_drzewa_przedzialowego < n) {
        podstawa_drzewa_przedzialowego <<= 1;
    }
    for (int i = 1; i <= n; ++i) {
        std::cin >> wysokosc >> wytrzymalosc;
        h[i] = std::make_pair(wysokosc, i);
        w[i] = std::make_pair(wytrzymalosc, i);
    }
 
    sort(h + 1, h + n + 1, wysokosc_maleje_index_rosnie);
 
    for (int i = 1; i <= n; ++i) {
        h[i].first = i-1;
    }
 
    sort(h + 1, h + n + 1, index_rosnie);
 
    for (int i = 1; i <= n; ++i) {
        dodaj_drzewo(h[i].first, w[i].first, podstawa_drzewa_przedzialowego);
        w[i].first = zapytanie_o_prawdziawa_wytrzymalosc(0, h[i].first, podstawa_drzewa_przedzialowego);
    }
 
    sort(w+1, w+n+1);
 
    for (int i = 1; i <= m; ++i) {
        std::cin >> s;
        wynik = 0;
        while (ostatnie_powalone_drzewo <= n) {
            if (w[ostatnie_powalone_drzewo].first > s) {
                break;
            } else {
                ostatnie_powalone_drzewo++;
                wynik++;
            }
        }
       std::cout << wynik << "\n";
    }
 
    return 0;
}
Kod C++ programu Halny, który jest omówiony w powyższym filmie i który otrzymuje 100%

 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz