\begin{yl}{2}{Vale kuju 1}{kuju1}{1 sek / 3 sek}{30 punkti}
\emph{Idee: Phil Labuschagne, teostus ja lahenduse selgitus: Ahto Truu}

\begin{quote}
Antud $A_1 < A_2 < \ldots < A_N$ ja $B_1 \le B_2 \le \ldots \le B_M$, kus $M, N \le 200\,000$.
Leida iga $i$ jaoks vähim $j$, mille korral $B_i \le A_j$.
\end{quote}

Esimene võimalus selle ülesande lahendamiseks on püstitusest lähtuv naiivne algoritm: võrdleme iga $i$ korral $B_i$ väärtust järjest $A_1, A_2, \ldots$ väärtustega, kuni leiame esimese $A_j$, mis pole väiksem kui $B_i$. Nii on tehtud failides \verb'sol_naive.py' ja \verb'sol_naive.cpp' toodud lahendustes, mis vaatavad iga $i$ väärtuse jaoks läbi keskmiselt pooled (ja halvimal juhul isegi kõik) $j$ väärtused ning kulutavad selleks kokku $O(M \cdot N)$ operatsiooni. See on piisav, et lahendada esimene alamülesanne, aga teises alamülesandes võivad $M$ ja $N$ mõlemad olla kuni $200\,000$ ja siis võib selle algoritmiga kuluda kuni $40\,000\,000\,000$ operatsiooni, mida on ajalimiiti mahtumiseks selgelt liiga palju.

Üks võimalus parema lahenduse saamiseks on kasutada ära, et jada $A$ on sorteeritud ja leida iga $i$ jaoks sobiv $j$ väärtus kahendotsinguga. Kahendotsing kulutab $N$-elemendilises jadas õige väärtuse leidmiseks $O(\log(N))$ võrdlemist ja seega kulub kokku $O(M \cdot \log(N))$ operatsiooni. Failides \verb'sol_bin_man_ok.py' ja \verb'sol_bin_man_ok.cpp' on kahendotsing programmeeritud ise, failides \verb'sol_bin_std_ok.py' ja \verb'sol_bin_std_ok.cpp' toodud lahendused kasutavad standardteegi funktsioone. Mõlemad variandid on piisavalt efektiivsed, et teenida maksimumpunktid.

Teine võimalus on kasutada ära, et mõlemad jadad on sorteeritud. See tähendab, et kui me oleme mingi indeksi $i$ jaoks juba leidnud indeksi $j$, mille korral $A_{j-1} < B_i \le A_j$, siis teame, et $i+1$ jaoks sobiv $j$ väärtus ei saa olla väiksem. Kuigi failides \verb'sol_merge_ok.py' ja \verb'sol_merge_ok.cpp' toodud lahendustes on kaks kordust üksteise sees, tasub tähele panna, et sisemine \verb'while'-kordus alustab iga kord sealt, kus eelmine \verb'while'-kordus lõpetas. Kui \verb'for'-kordus käib läbi $M$ erinevat $i$ väärtust, käivad kõik \verb'while'-korduse käivitused \emph{kokku} läbi $N$ erinevat $j$ väärtust ja seega kulutab selline kahe jada paralleelse läbimise algoritm $O(M + N)$ operatsiooni.

Kas efektiivsem on kahendotsinguga või jadade paralleelse läbimisega lahendus, sõltub sisend\-andmetest. Kui $M$ ja $N$ on samas suurusjärgus, on efektiivsem paralleelse läbimisega lahendus. Kui $M$ on palju väiksem kui $N$, siis otseselt vastuse arvutamine on efektiivsem kahendotsinguga. Aga samas tuleb tähele panna, et andmete sisse lugemiseks tuleb igal juhul teha $O(M + N)$ operatsiooni, seega siin ülesandes ei saa programmi kogutööaeg isegi $M$ ja $N$ ebavõrdsuse korral sellest väiksem olla.

\end{yl}
