Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | secventa.in, secventa.out | Sursă | preOJI 2004 |
| Autor | Mircea Bogdan Pasoi | Adăugată de | |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   2/5 |
Vezi solutiile trimise | Statistici
Secventa
 Testele pentru aceasta problema nu sunt destul de bine construite pentru a departaja corect solutii ineficiente sau gresite.Intra aici daca vrei sa ne ajuti sa imbunatatim calitatea testelor pentru aceasta problema! |
Gigel are un sir de N numere intregi. Toata lumea stie ca o secventa este un subsir de numere care apar pe pozitii consecutive in sirul initial. Gigel a definit baza unei secvente ca fiind minimul valorilor elementelor din secventa respectiva.
Cerinta
Fiind dat un numar natural K, determinati pentru Gigel o secventa de lungime cel putin K cu baza maxima.
Date de intrare
Fisierul de intrare secventa.in contine pe prima linie numerele N si K, separate prin spatiu. Pe cea de a doua linie se afla elementele sirului separate prin cate un spatiu.
Date de iesire
Fisierul de iesire secventa.out trebuie sa contina o singura linie cu trei numere: pozitia de inceput si de sfarsit a secventei de lungime cel putin K cu baza maxima si valoarea maxima a bazei.
Restrictii si precizari
- 1 ≤ K ≤ N ≤ 500 000
- Elementele din vector sunt numere intregi din intervalul [-30 000, 30 000]
- Daca exista mai multe solutii pentru care se obtine baza maxima, atunci se va alege cea in care pozitia de inceput a secventei este cea mai mica, iar in caz de egalitate cea in care pozitia de sfarsit a secventei este cea mai mica
Exemplu
| secventa.in | secventa.out |
|---|---|
| 8 3 -1 2 3 1 0 4 8 6 | 6 8 4 |
Explicatii
Secventa care incepe pe pozitia 6 si se termina pe pozitia 8 (de lungime 3) este (4, 8, 6) are baza minim(4, 8, 6) = 4. Nu mai exista o secventa cu lungime mai mare sau egala cu 3 care sa aiba baza mai mare.
