Par impar

Time limit: 0.6s Memory limit: 128MB Input: parimpar.in Output: parimpar.out

Pentru un șir a1,a2,,aNa_1, a_2, \dots, a_N de numere întregi vrei să aplici o secvență de operații astfel încât să obții un nou șir bb, tot de lungime NN. Inițial șirul bb este vid.

Într-o operație faci una dintre următoarele:

  1. Alegi toate pozițiile pare (2,4,6,2, 4, 6, \dots) din aa și le adaugi în această ordine la finalul șirului bb. După aceea ștergi toate aceste elemente din aa. Această operație se poate aplica doar dacă șirul aa mai conține cel puțin 22 elemente (observați că dacă șirul aa ar avea un singur element atunci aplicânda această operație, nu s-ar schimba nici aa, nici bb).
  2. Alegi toate pozițiile impare (1,3,5,1, 3, 5, \dots) din aa și le adaugi în această ordine la finalul șirului bb. După aceea ștergi toate aceste elemente din aa. Această operație se poate aplica indiferent de lungimea șirului aa.

Operațiile se repetă până ce șirul aa devine vid.

De exemplu, pentru șirul [1,2,3,4,5,6,7,8,9,10][1, 2, 3, 4, 5, 6, 7, 8, 9, 10], o secvență validă de operații este 1,2,2,21, 2, 2, 2.

a:[1,2,3,4,5,6,7,8,9,10]1[1,3,5,7,9]2[3,7]2[7]2[]a: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] \xrightarrow[]{1} [1, 3, 5, 7, 9] \xrightarrow[]{2} [3, 7] \xrightarrow[]{2} [7] \xrightarrow[]{2} [].

b:[]1[2,4,6,8,10]2[2,4,6,8,10,1,5,9]2[2,4,6,8,10,1,5,9,3]2[2,4,6,8,10,1,5,9,3,7]b: [] \xrightarrow[]{1} [2, 4, 6, 8, 10] \xrightarrow[]{2} [2, 4, 6, 8, 10, 1, 5, 9] \xrightarrow[]{2} [2, 4, 6, 8, 10, 1, 5, 9, 3] \xrightarrow[]{2} [2, 4, 6, 8, 10, 1, 5, 9, 3, 7].

Se observă că ultima operație, este obligatoriu de tipul 22, deoarece șirul aa conținea un singur element (pe 77).

Cerință

Se dă NN, șirul aa și QQ întrebări de forma L RL \ R. Să se spună pentru fiecare întrebare în câte moduri putem aplica operațiile astfel încât LSbRL \leq S_b \leq R, unde SbS_b este suma maximă a unei subsecvențe din bb.

Date de intrare

Pe prima linie a fișierului parimpar.in se află numerele întregi N,QN, Q în ordinea aceasta.
Pe a doua linie se află șirul a1,a2,,aNa_1, a_2, \dots, a_N.
Pentru fiecare ii de la 11 la QQ, pe linia i+2i + 2 se află câte două numere, LL și RR, reprezentând cea de a ii-a întrebare.

Date de ieșire

În fișierul parimpar.out se vor afișa QQ linii. Pe linia ii se va afla un singur număr natural, reprezentând răspunsul la întrebarea ii.

Restricții și precizări

  • 1N,Q21051 \leq N, Q \leq 2 \cdot 10^5;
  • 109ai109-10^9 \leq a_i \leq 10^9
  • Subsecvențele vide se numără și ele, așadar subsecvența de sumă maximă a unui șir are valoarea cel puțin 00.
# Punctaj Restricții
1 22 N15,Q100N \leq 15, Q \leq 100
2 42 N,Q2 000N, Q \leq 2 \ 000
3 36 Fără alte restricții

Exemplu

parimpar.in

8 4
3 -4 5 8 -6 2 -11 7
0 15
17 17
2 100
17 21

parimpar.out

1
3
8
5

Explicație

Aplicând secvența de operații 2,1,2,22, 1, 2, 2 obținem b=[3,5,6,11,8,7,4,2]b = [3, 5, -6, -11, 8, 7, -4, 2]. Sb=8+7=15S_b = 8 + 7 = 15. La prima întrebare, aceasta este singura secvență de operații validă.

Aplicând secvența de operații 1,2,1,21, 2, 1, 2, obținem b=[4,8,2,7,3,6,11,5]b = [-4, 8, 2, 7, 3, -6, -11, 5]. Sb=8+2+7+3=20S_b = 8 + 2 + 7 + 3 = 20. Aceasta contribuie la ultimele două întrebări.

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