partition

Time limit: 0.5s Memory limit: 512MB Input: partition.in Output: partition.out

Cerință

Fie SS un şir de QQ numere întregi. O subsecvenţă [X,Y][X, Y] a şirului SS, 0XYQ10 \leq X \leq Y \leq Q-1, se defineşte ca o secvenţă de elemente consecutive SX,SX+1,,SYS_X, S_{X+1}, \dots, S_Y. Costul unei subsecvenţe se defineşte ca fiind valoarea minimă a unui element din aceasta. O partiție a şirului SS se definește ca o împărţire a lui SS în subsecvenţe astfel încât fiecare element al şirului aparţine exact unei subsecvente. Daca partiția este formată din kk subsecvențe, scorul acesteia se definește ca fiind suma costurilor celor kk subsecvențe.

Se dă un șir VV de N(1N200 000)N (1 \leq N \leq 200 \ 000) numere întregi, 109Vi109-10^9 \leq V_i \leq 10^9. Se cere să se răspundă, pentru MM întrebări de forma XiX_i, YiY_i, care este maximul dintre scorurile tuturor partițiilor subsecvenței [Xi,Yi][X_i, Y_i]

Important! Deşi valorile elementelor şirului VV nu sunt generate aleator, ordinea acestora în sir este aleatoare.

Date de intrare

Fișierul de intrare partition.in are urmatoarea structură:

  • linia 11: N MN \ M, reprezentând lungimea sirului VV, respectiv numărul de întrebări
  • linia 22: V0 V1VN1V_0 \ V_1 \dots V_{N-1}, cele NN elemente ale șirului VV.
  • linia 3+i3 + i (0iM1)(0 \leq i \leq M-1): Xi YiX_i \ Y_i reprezentând cele MM întrebari.

Date de ieșire

Fișierul de ieșire partition.out va conține MM linii, pe fiecare dintre acestea se va găsi un singur număr întreg, maximul dintre scorurile tuturor partițiilor subsecvenței [Xi,Yi][X_i, Y_i].

Restricții și precizări

  • 1N,M200 0001 \leq N, M \leq 200 \ 000;
  • 109Vi109-10^9 \leq V_i \leq 10^9;
  • Pentru teste în valoare de 66 puncte, 1N,M501 \leq N, M \leq 50
  • Pentru teste în valoare de alte 77 puncte, 1N4001 \leq N \leq 400, 1M16 0001 \leq M \leq 16 \ 000
  • Pentru teste în valoare de alte 3838 puncte, 1N2 0001 \leq N \leq 2 \ 000
  • Testele nu sunt cele din timpul concursului

Exemplu

partition.in

7 3
3 -2 5 -2 -4 1 -2
0 6
2 4
4 6

partition.out

2
1
-4

Explicație

Pentru primul exemplu, avem un șir format din N=7N = 7 elemente și M=3M = 3 întrebări.

O partiție optimă a subsecventei [0,6][0, 6] este următoarea: (3),(2),(5),(2,4,1,2)(3),(−2),(5),(−2, −4, 1, −2), iar scorul acesteia este 22, dat de suma costurilor subsecvențelor (3,2,5,4)(3, -2, 5, -4).

O partiție optimă a subsecventei [2,4][2, 4] este următoarea: (5),(2,4)(5),(−2, −4), iar scorul acesteia este 11, dat de suma costurilor subsecvențelor (5,4)(5, -4).

O partiție optimă a subsecventei [4,6][4, 6] este următoarea: (4,1,2)(−4, 1, −2), iar scorul acesteia este 4−4, dat de suma costurilor subsecvențelor (4)(-4).

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