Fişierul intrare/ieşire:eq.in, eq.outSursăAutumn Warmup 2006
AutorVlad BerteanuAdăugată de
Timp execuţie pe test0.85 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Easy Query

Se considera un sir de N numere naturale, x1, x2, ... xN. Se defineste urmatoarea operatie:

  • pentru o pereche i,j, 1 ≤ i ≤ j ≤ N, se considera secventa xi, xi+1, ... xj
  • se construiesc doua siruri corespunzatoare secventei date, astfel:
    • yt = xt - xk + xp, i ≤ t ≤ j, t ≤ k ≤ j, t ≤ p ≤ j, unde yt este maxim
    • zt = xt - xk + xp, i ≤ t ≤ j, t ≤ k ≤ j, t ≤ p ≤ j, unde zt este minim
  • se calculeaza valoarea P = max(y) + min(z), unde max(y) este maximul din sirul y construit ca mai sus, iar min(z) minimul din sirul z.

Cerinta

Dandu-se sirul initial, sa se raspunda la un set de mai multe operatii.

Date de Intrare

Pe prima linie a fisierului de intrare eq.in se gasesc doua numere N si M reprezentand numarul de elemente ale sirului x, respectiv numarul operatiilor pentru care se doreste determinarea valorii P. Pe urmatoarea linie se afla elementele sirului x separate prin cate un caracter spatiu. Urmatoarele M linii contin subsecventele definite prin doi intregi i si j separati prin spatiu reprezentand pozitia de inceput, respective pozitia de sfarsit a subsecventei.

Date de Iesire

Fisierul de iesire eq.out contine valorile P pentru fiecare subsecventa data, cate una pe linie, in ordinea aparitiei acestora in fisierul de intrare.

Restrictii si precizari

  • 1 < N ≤ 100 001
  • 1 < M ≤ 130 001
  • 0 ≤ xi ≤ 224

Exemplu

eq.ineq.out
6 3
1 8 10 5 9 3
1 4
2 6
3 5
7
16
16
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content