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;
}