Fișierul intrare/ieșire: nrapp.in, nrapp.out Sursă Cerc informatica Tudor Vianu
Autor din folclor Adăugată de teodor94Teodor Plop teodor94
Timp execuție pe test 0.25 sec Limită de memorie 4096 KB
Scorul tău N/A Dificultate normalnormalnormalnormalnormal

Vezi soluțiile trimise | Statistici

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