Fişierul intrare/ieşire:secvmax.in, secvmax.outSursăAlgoritmiada 2009, Runda 3
AutorCosmin GheorgheAdăugată degcosminGheorghe Cosmin gcosmin
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Secvmax

Fiona are o secventa de N numere naturale. Ea se intreaba din cand in cand pentru un anumit numar Q care este cea mai lunga subsecventa care are toate numerele mai mici sau egale cu Q. Ajutati-o pe Fiona sa isi rapunda la toate intrebarile.

Date de intrare

Fişierul de intrare secvmax.in contine pe prima linie doua numere separate printr-un spatiu N si M ce reprezinta lungimea secventei initiale si numarul de intrebari ale Fionei. Urmatoarea linie contine cele N numere naturale separate printr-un spatiu fiecare. Urmatoarele M linii contin fiecare cate un numar Q reprezentand intrebarile Fionei.

Date de ieşire

Fişierul de iesire secvmax.out va contine M linii reprezentand raspunsurile la intrebarile Fionei. Mai exact linia i contine raspunsul la a i-a intrebare si anume lungimea celei mai lungi subsecvente care are toate numerele mai mici sau egale cu Qi.

Restricţii

  • 1 ≤ N, M ≤ 105
  • Toate numerele din fisierul de intrare vor fi cuprinse intre 0 si 109

Exemplu

secvmax.insecvmax.out
5 3
4 2 3 5 1
1
3
4
1
2
3

Explicaţie

Raspunsurile pentru fiecare intrebare reprezentate prin numerele ingrosate:

  • 1 -> 4 2 3 5 1
  • 3 -> 4 2 3 5 1
  • 4 -> 4 2 3 5 1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content