Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | inversari.in, inversari.out | Sursă | Algoritmiada 2010, Runda Finala |
| Autor | Adrian Airinei | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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 situata 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 intregi pe 32 biti
Exemplu
| inversari.in | inversari.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
