Fişierul intrare/ieşire:saracsaurege.in, saracsaurege.outSursăHappy Birthday Infoarena 2014
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test1 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Sarac Sau Rege

Se da un sir cu N elemente si M query-uri. Pentru fiecare query se dau 2 valori a si b, iar Zeul Valorii trebuie sa decida daca secventa este Sarac sau Rege. Pentru asta, voi trebuie sa afisati valoarea maxima din acea secventa.

Date de intrare

Fişierul de intrare saracsaurege.in va contine pe prima linie 2 numere naturale N si M. Pe linia 2 vor fi N numere reprezentand sirul dat. Urmatoarele M linii vor contine cate 2 numere a si b, reprezentand query-urile sortate dupa b - a.

Date de ieşire

Fişierul de ieşire saracsaurege.out va contine M valori reprezentand raspunsul la cele M query-uri.

Restricţii

  • 1 ≤ N ≤ 50.000
  • 1 ≤ M ≤ 1.000.000
  • Cele M query-uri sunt sortate descrescator dupa b - a.
  • Atentie la limita de memorie!
  • Incercati sa rezolvati problema cu O(n * log n + m) timp si O(n) memorie :)

Exemplu

saracsaurege.insaracsaurege.out
5 3
7 6 9 3 8
2 5
1 2
4 4
9
7
3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?