Unirea pentru Performanta - Online | fuziune

This was the problem page during the contest. Access the current page here.
Time limit: 0.4s Memory limit: 128MB Input: fuziune.in Output: fuziune.out

Armata albastră a primit sarcina de a proteja legendarele cuburi ale dragonului. Pentru a le face treaba mai ușoară, aceștia au primit două inele fermecate cu abilitatea de a fuziona luptătorii care le poartă. Când 22 luptători fuzionează, puterea luptătorului rezultat este egală cu suma celor două puteri inițiale, la care se adaugă produsul acestora. Formal, dacă cei doi luptători au puterile aa respectiv bb, atunci după fuzionare vor avea puterea a+b+aba + b + a * b. Generalul Abelius are nevoie ajutorul vostru pentru a testa puterea armatei albastre.

Cerință

Se dă un vector format din NN numere naturale reprezentând puterile luptătorilor din armata albastră, și QQ interogări formate din câte o pereche de numere naturale sis_i și did_i. Vi se cere să aflați puterea luptătorilor din intervalul [si,di][s_i, d_i], dacă aceștia ar fuziona folosind inelele fermecate. Fuzionarea acestora se face în ordinea indicilor, de la stânga la dreapta: cei doi luptători cei mai din stânga fuzionează, apoi rezultatul fuzionează cu cel de-al 3-lea etc.

Date de intrare

Pe prima linie a fișierului de intrare fuziune.in se găsesc 22 numere NN și QQ reprezentând numărul de luptători din armata albastră, respectiv numărul de interogări ale generalului Abelius.
Pe a doua linie se vor găsi NN numere naturale aia_i, fiecare reprezentând puterea luptătorului de pe poziția ii.
Pe următoarele QQ linii se vor găsi QQ perechi de numere naturale sis_i și did_i, câte o pereche pe câte o linie, reprezentând capetele intervalului pentru cea de-a ii-a interogare.

Date de ieșire

În fișierul de ieșire fuziune.out se vor găsi QQ numere, fiecare pe câte o linie, cel de-al ii-lea număr reprezentând răspunsul la cea de-a ii-a interogare. Deoarece rezultatul poate fi foarte mare se cere afișarea acestuia modulo 109+710^9+7.

Restricții și precizări

  • 1N,Q1 000 0001 \leq N, Q \leq 1 \ 000 \ 000;
  • 1sidiN1 \leq s_i \leq d_i \leq N;
  • 1ai1 000 000 0001 \leq a_i \leq 1 \ 000 \ 000 \ 000;
# Punctaj Restricții
1 15 1N,Q5 0001 \leq N, Q \leq 5 \ 000
2 25 1N,Q50 0001 \leq N, Q \leq 50 \ 000
3 30 1N,Q500 0001 \leq N, Q \leq 500 \ 000
4 30 1N,Q1 000 0001 \leq N, Q \leq 1 \ 000 \ 000

Exemplul 1

fuziune.in

10 5
2 5 7 3 1 3 5 6 9 2
1 4
3 5
8 10
5 5
4 7

fuziune.out

575
63
209
1
191

Explicație

Pentru prima interogare pornim de la intervalul [1,4][1, 4], format din elementele {2,5,7,3}\{2, 5, 7, 3\}.
Prima fuziune: 2+5+25=172 + 5 + 2 * 5 = 17.
Elementele din interval devin {17,7,3}\{17, 7, 3\}.
A doua fuziune: 17+7+177=14317 + 7 + 17 * 7 = 143.
Elementele devin {143,3}\{143, 3\}.
A treia fuziune: 143+3+1433=575143 + 3 + 143 * 3 = 575.
Rezultatul pentru prima interogare este 575575.

Log in or sign up to be able to send submissions!