Imi poate acorda si mie cineva o indicatie amcar la cum se rezolva problema asta?
Fie N un număr natural şi un şir de 2N numere naturale X1, X2, …, X2N.
Cerinţa
Trebuie să răspundeţi la un număr de Q întrebări de forma : Date k şi p, care este elementul maxim dintre elementele Xk, Xk+1, …, Xp din şir?
Date de intrare:
Pe prima linie a fişierului maxim.in se află N, pe următoarea linie 2N numere separate prin câte un spaţiu reprezentând elementele şirului. Pe linia a treia se află Q, numărul de întrebări, iar pe următoarele Q linii sunt câte două numere k şi p separate printr-un spaţiu reprezentând capetele secvenţei din care trebuie să aflaţi maximul.
Date de ieşire
Fişierul maxim.out conţine exact Q linii. Pe fiecare linie se află un singur număr S, reprezentând răspunsul la fiecare întrebare din fişierul de intrare.
Restricţii şi precizări
• 2 N 13
• Xi este un număr între 1 şi 30.000, pentru orice i, 1 i 2N
• 1 k p 2N
• 1 Q 100.000
Exemplu:
maxim.in
2
4 6 7 1
3
1 4
1 2
2 4 maxim.out
7
6
7 Explicaţie:
Dintre elementele de la poziţia 1 la 4, maximul este 7.
Dintre elementele de la poziţia 1 la 2, maximul este 6.
Dintre elementele de la poziţia 2 la 4, maximul este 7.