_Error 404: Poveste not found_
Fie S un sir de Q numere intregi. O subsecventa [X, Y] a sirului S , 0 ≤ X ≤ Y ≤ Q-1 , se defineste ca o secventa de elemente consecutive S[~X~], S[~X+1~],....,S[~Y~]. Costul unei subsecvente se defineste ca fiind valoarea minima a unui element din aceasta. O partitie a sirului S se defineste ca o impartire a lui S in subsecvente astfel incat fiecare element al sirului apartine exact unei subsecvente. Daca partitia este formata din k subsecvente, scorul acesteia scorul acesteie se defineste ca fiind suma costurilor celor k subsecvente.
Fie _S_ un sir de _Q_ numere intregi. O subsecventa [_X_, _Y_] a sirului _S_ , 0 ≤ _X_ ≤ _Y_ ≤ _Q-1_ , se defineste ca o secventa de elemente consecutive S ~X~, S ~X+1~,....,S ~Y~. Costul unei subsecvente se defineste ca fiind valoarea minima a unui element din aceasta. O partitie a sirului _S_ se defineste ca o impartire a lui _S_ in subsecvente astfel incat fiecare element al sirului apartine exact unei subsecvente. Daca partitia este formata din _k_ subsecvente, scorul acesteia scorul acesteie se defineste ca fiind suma costurilor celor _k_ subsecvente.
Se da un sir V de N (1 ≤ N ≤ 200 000) numere intregi , -10^9^ ≤ V[~i~] ≤ 10^9^. Se cere să se răspundă, pentru M întrebări de forma X[~i~] , Y[~i~] , care este maximul dintre scorurile tuturor partitiilor subsecventei [X[~i~], Y [~i~]]
Se da un sir _V_ de _N_ (1 ≤ _N_ ≤ 200 000) numere intregi , -10^9^ ≤ V ~i~ ≤ 10^9^. Se cere să se răspundă, pentru M întrebări de forma _X ~i~_ , _Y ~i~_ , care este maximul dintre scorurile tuturor partitiilor subsecventei [_X ~i~_ , _Y ~i~_]
*Important! Desi valorile elementelor sirului V nu sunt generate aleator, ordinea acestora în sir este aleatoare.*
h2. Date de intrare
*linia 1: N M, reprezentand lungimea sirului V, respectiv numarul de intrebari
*linia 2: V[~0~] V[~1~] ... V[~N-1~], cele N elemente ale sirului V.
*linia 3 + i (0 ≤ i ≤ M-1): X[~i~] Y[~i~] reprezentand cele M intrebari.
h2. Detalii de implementare
Trebuie sa implementati urmatoarea functie :
std::vector<long long> find_partitions(std::vector<int> V, std::vector<int> X, std::vector<int> Y);
h2. Punctare
|_. Subtask |_. Punctaj |_. Constrangeri|
| Subtask | Punctaj | Constrangeri|
|1 |6 puncte | 1 ≤ _N_ ≤ 50 , 1 ≤ _M_ ≤ 50 |
|2 |7 puncte | 1 ≤ _N_ ≤ 400 , 1 ≤ _M_ ≤ 16000|
|3 |38 puncte | 1 ≤ _N_ ≤ 2000 , 1 ≤ _M_ ≤ 200 000|
|4 |49 puncte | 1 ≤ _N_ ≤ 200 000 , 1 ≤ _M_ ≤ 200 000|
h2. Model de grader
Vi se pune la dispozit, ie un grader pentru a vă putea compila s, i testa codul local. Acesta va citi de la
consolă datele de intrare în următorul format:
* linia 1: _N_ _M_ , reprezentand lungimea sirului V ,respectiv numarul de intrebari
* linia 2: _V ~0~_ _V ~1~_ .... _V ~N-1~_ , cele _N_ elemente ale sirului _V_
* linia 3: 3+i (0 ≤ i ≤ _M-1_): _X ~i~_ _Y ~i~_ reprezentand cele _M_ intrebari
h2. Exemplu
table(example). |_. Intrare |_. Iesire |
