| Fişierul intrare/ieşire: | temple.in, temple.out | Sursă | Infoarena Monthly 2014, Runda 8 |
| Autor | Andrei Heidelbacher | Adăugată de |  Heidelbacher Andrei •a_h1926 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Temple
Tassadar vrea să exploreze un templu Xel’Naga, dar pentru a putea intra, trebuie să introducă un cod secret. În urma unor calcule matematice, a făcut câteva observaţii cu ajutorul cărora poate descoperi codul secret.
Fie o constantă K şi un şir V de N numere întregi. Fiecare poziţie i din şir are asociat un cost Ci. Definim Nexti = max(i, min(j | i < j, Vi < Vj)), iar NextiP = NextNextiP – 1.
Fie şirul S de N numere întregi, Si = max(Ci, CNexti, CNexti2, ..., CNextiK - 1). Codul secret este chiar şirul S!
Tassadar a reuşit să pătrundă în templul Xel’Naga. Voi puteţi?
Date de intrare
Fişierul de intrare temple.in conţine pe prima linie două numere întregi N şi K cu semnificaţia din enunţ. Pe a doua linie se află N numere întregi Vi reprezentând şirul V. Linia următoare conţine N numere întregi Ci reprezentând costurile poziţiilor din şirul V.
Date de ieşire
În fişierul de ieşire temple.out veţi afişa pe prima linie N numere întregi Si reprezentând codul secret.
Restricţii
- 1 ≤ K ≤ N ≤ 105
- -109 ≤ Vi ≤ 109
- -1015 ≤ Ci ≤ 1015
Exemplu
| temple.in | temple.out |
|---|---|
| 4 2 2 3 1 4 5 6 1 2 | 6 6 2 2 |
Explicaţie
Şirul Next este {2, 4, 4, 4}, iar şirul S este {max(5, 6), max(6, 2), max(1, 2), max(2)} = {6, 6, 2, 2}.
