Fişierul intrare/ieşire:inversari.in, inversari.outSursăAlgoritmiada 2010, Runda Finala
AutorAdrian AirineiAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Inversari

Pe langa vechile lui pasiuni artistice, Zuru are acum o pasiune pentru inversari. Profesorul sau de filosofie ii pune la dipozitie o secventa A care contine N numere naturale. Apoi ii pune M intrebari de forma: cate inversari contine subsecventa din sirul A aflata intre pozitiile i si j? (i ≤ j). Pentru ca este un perfectionist, Zuru va cere ajutorul pentru a raspunde la fiecare din intrebarile puse de profesor. Zuru s-a gandit ca ar fi bine sa va spuna si cum defineste el o inversare. In viziunea sa o inversare este o pereche de indici (p, q) cu p < q astfel incat Ap > Aq.

Date de intrare

Fişierul de intrare inversari.in contine pe prima linie N si M, separate de un singur spatiu, avand semnificatie din enunt. Urmatoarea linie contine cele N numere naturale ale secventei A, separate prin cate un singur spatiu. Pe urmatoarele M linii se afla intrebarile puse de profesor, pe fiecare linie aflandu-se doua numere separate printr-un spatiu, i si j (i ≤ j), capetele subsecventei.

Date de ieşire

În fişierul de ieşire inversari.out se afla M linii, pe fiecare linie veti afisa raspunsul la intrebarile profesorului, in ordinea in care acestea apar in fisierul de intrare.

Restricţii

  • 1 ≤ N ≤ 5000
  • 1 ≤ M ≤ 100 000
  • Elementele secventei A sunt numere naturale mai mici sau egale decat 100 000
  • Pentru 50% din teste N ≤ 1000
  • Pentru 50% din teste elementele secventei A sunt numere naturale mai mici sau egale decat 30

Exemplu

inversari.ininversari.out
5 5
4 2 5 3 1
1 5
2 4
3 5
1 3
2 3
7
1
3
1
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content