Wieże

Robiłem zadanie, które z początku wydawało mi się banalne, zabrało mi wiele dni na rozmyślanie jak je wykonać i po zrobieniu go na tak zwaną "piechotę" czyli linowym przeszukiwaniu tablicy właśnie te kilka dni rozmyślam jak wykonać szukanie binarne w tym przypadku, gdyż nie wiem co zrobić gdy element nie znajduje się w tablicy a muszę podać jakąś wartość i pomimo kombinowania z wieloma ifami do niczego nie doszedłem. Z wyszukiwaniem binarnym nigdy nie miałem do czynienia więc znam tylko samą zasadę działania ale właśnie problem tkwi w tym, że nie wiem do zrobic z elementami które w tablicy się nie pojawiają.
Oto zadanie:

W Bajtocji wybudowano wysoką wieżę. Wejście na wieżę składa się z schodków, a każdy schodek ma pewną wysokość.

Bajtocką wieżę chce odwiedzić mieszkańców. Każda z osób posiada pewien wzrost, który pomaga w pokonywaniu kolejnych schodków. Aby mieszkaniec Bajtocji mógł wejść na pewien schodek, to musi być wyższy od wysokości schodka. Jeśli pewien schodek jest nie do przejścia przez mieszkańca, to zatrzymuje się on w danym miejscu na wieży - wyżej nie będzie mógł wejść.

Znając wysokości kolejnych schodków i osób zwiedzających wieżę chcielibyśmy wiedzieć, w którym miejscu zatrzyma się każdy mieszkaniec Bajtocji.

Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite (), oznaczające odpowiednio liczbę schodków prowadzących na wieżę oraz liczbę mieszkańców chcących odwiedzić wieżę. Kolejny wiersz zawiera liczb całkowitych () , gdzie oznacza wysokość -tego schodka. Pierwszy schodek znajduje się na samym dole wieży, a każdy kolejny wyżej od poprzednich. Następny wiersz wejścia zawiera liczb całkowitych ( ), gdzie oznacza wzrost -tego mieszkańca.

Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać liczb całkowitych , gdzie oznacza maksymalny numer schodka, na który może wejść -ty mieszkaniec Bajocji.

Przykład
Dla danych wejściowych:

3 6
2 5 1
1 2 3 4 5 6
poprawną odpowiedzią jest:

0 0 1 1 1 3

Pomysł który mi przychodzi do głowy:
Mając taki ciąg
2 5 1 7 5 6 11 4 3
Zamieniamy go na
2 5 5 7 7 7 11 11 11
I wyszukujemy binarnie (pewnie lower_bound).
Każdy element zawiera wtedy wartość najwyższego dotychczas stopnia.
Próbowałeś coś takiego? Ja bym to tak spróbował.

Sortowalem elementy by ciąg byl niemalejacy i koncepcja wtedy jest dobra bo wtedy szukamy schodka wiekszego badz równego wysokości mieszkańca czyli ze schodów wysokosci 1 5 3 2 7 6 8 jest ciąg 1 5 5 5 7 7 8 czyli tak jak mówisz ale nie wiem jak tu zastosowac wyszukiwanie binarne. Nie mam pojęcia coz to lower_,bound i jak sie to stosuje

lower_bound. W dokumentacji jest podany mały przykład. Jeżeli korzystasz z std::vector, to przekazujesz vec.begin(), vec.end() i dostajesz iterator na szukany element, natomiast jeżeli masz tablicę na wskaźnikach to przekazujesz arr, arr+n i dostajesz wskaźnik na szukany element. Jeżeli nie znasz jeszcze std::vector, to polecam się zapoznać.
Zwróć też uwagę na opis wartości zwracanej:

An iterator to the lower bound of val in the range.
If all the element in the range compare less than val, the function returns last.

EDIT:
Jeżeli nie znasz jeszcze za bardzo typów i algorytmów biblioteki cpp to mogę polecić fragment tego kursu:
https://main2.edu.pl/main2/courses/show/7/5/
Zawiera opis wyszukiwania binarnego i wyszukiwania binarnego pierwszego wystąpienia elementu w tablicy.

Dla każdego bajtocjanina szukasz od początku pierwszy schodek który jest wyższy od niego i przed tym schodkiem bajtocjanin się zatrzyma.
Więc:

• wpisz do set'a wszystkie wysokości bajtocjaninów.
• zaczynasz od najniższego bajtocjanina oraz pierwszego schodka, szukasz gdzie się zatrzyma i dopisujesz do mapy wzrost -> nr schodka
• przechodzisz do kolejnego bajtocjanina, i kontynuujesz od bierzącego schodka wynik do mapy i tak dalej
  Koszt: O(max(ilość schodków,ilość bajtocjan))