Fişierul intrare/ieşire: | secvmax.in, secvmax.out | Sursă | Algoritmiada 2009, Runda 3 |
Autor | Cosmin Gheorghe | Adăugată de | |
Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
Scorul tău | N/A | Dificultate | N/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.in | secvmax.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