Fişierul intrare/ieşire:secventa.in, secventa.outSursăpreOJI 2004
AutorMircea Bogdan PasoiAdăugată de
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.insecventa.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content