Atenție! Aceasta este o versiune veche a paginii., scrisă la 2013-01-25 21:17:29.
Revizia anterioară   Revizia următoare  

Fișierul intrare/ieșire nrapp.in, nrapp.out Sursă Cerc informatica Tudor Vianu
Autor din folclor Adăugată de avatar teodor94 Teodor Plop teodor94
Timp de execuție pe test 0.25 sec Limită de memorie 4096 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Numere Apropiate (clasa a 7-a)

Se da un numar natural N si un sir v de N numere naturale. Sa se raspunda la Q intrebari de genul:

  • “D y”: Care este cea mai mica pozitie x, unde x > y, pentru care v[x] < v[y] ? Daca nu exista o astfel de pozitie, raspunsul acestei intrebari este N + 1.
  • “S y”: Care este cea mai mare pozitie x, unde x < y, pentru care v[x] < v[y] ? Daca nu exista o astfel de pozitie, raspunsul acestei intrebari este 0.

Date de intrare

Fișierul de intrare nrapp.in contine pe prima linie un numar natural N, urmat in cea de-a doua linie un sir de N numere naturale. Pe cea de-a treia linie se afla numarul natural Q, iar pe urmatoarele Q linii se gasesc codificarile celor Q intrebari la care trebuie sa raspundeti.

Date de ieșire

În fișierul de ieșire nrapp.out se vor gasi Q linii, linia i continand raspunsul la intrebarea i.

Restricții

  • 1 ≤ N ≤ 100.000
  • 1 ≤ Q ≤ 100.000
  • 1 ≤ v[i] ≤ 1.000

Exemplu

nrapp.in nrapp.out
8 1 3 6 5 2 1 9 6 8 S 1 D 2 D 3 S 4 S 5 D 6 D 7 D 8
0 5 4 2 1 9 8 9

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii