Chițooc

chitooc

== include(page="template/taskheader" task_id="chitooc") ==

Eşti antrenorul echipei ZOMVS şi te afli în satul Chiţooc la finala turneului de fotbal. Este minutul 90' şi echipa ta are avantaj, când deodată nişte vaci invadează terenul!
 
Terenul este împărţit în $N$ zone de lungime egală, iar numărul de vaci din fiecare zonă este cunoscut (zonele terenului pot fi reprezentate ca un vector de $N$ elemente).
 
Fiindcă ai prevăzut situaţia aceasta, *fiecare* dintre jucătorii echipei tale are un lasou cu care poate face următoarea mişcare *cel mult o singură* dată:
 
* Dacă jucătorul $i$ se află pe poziţia $pos{~i~}$, el poate să adune toate vacile dintr-o zonă $j$ în zona $pos{~i~}$, cu condiţia ca $j < pos{~i~}$.
* Totuşi, această mişcare consumă energia jucătorului respectiv. Dacă coeficientul energiei jucătorului este $coef{~i~}$, mişcarea va consuma $coef{~i~} * (pos{~i~} - j)$ unităţi de energie.
 
h2. Cerinţă
 
Fiindcă tu eşti antrenorul lor, primeşti $Q$ întrebări de la jucători. Pentru fiecare întrebare primeşti două valori $l$, $r$ şi te întreabă care este numărul maxim de vaci care pot fi strânse într-o zonă şi care este energia totală minimă necesară pentru a atinge acest număr folosind doar zone din intervalul $[l, r]$.
 
h3. Generarea datelor
 
Pentru a evita citirea unui volum foarte mare de date, doar primele $M$ întrebări vor fi citite din fişierul de intrare (unde $M &le; 10 000$). Restul întrebărilor, de la $M + 1$ până la $Q$, se vor genera în programul vostru folosind următorul algoritm:
 
== code(c) |
pentru i ← M + 1, Q execută
    l[i] ← ((l[i - 1] ^ (a * l[i - M])) mod N) + 1
	r[i] ← ((r[i - 1] ^ (b * r[i - M])) mod N) + 1
	dacă l[i] > r[i] atunci
		interschimbă l[i] cu r[i]
	sfârşit dacă
sfârşit pentru
==
 
*Notă:* Operaţia logică pe biţi „XOR / SAU exclusiv” este reprezentată de simbolul $&#94;$ şi se efectuează în C/C++ prin operatorul $&#94;$. Calculele intermediare din algoritmul de generare a datelor pot depăşi capacitatea de reprezentare a tipurilor întregi pe 32 de biţi (de exemplu $int$ sau $unsigned int$). Se recomandă utilizarea tipurilor de date pe $64$ de biţi (de exemplu $long long$) unde este cazul.

Poveste şi cerinţă...

h2. Date de intrare

Pe prima linie se dă $N$ (numărul de zone) şi $K$ (numărul de jucători). Pe următoarea linie se află $N$ numere reprezentând numărul de vaci de pe fiecare zonă. Pe următoarele $K$ linii se află două valori: $pos$ şi $coef$, reprezentând poziţia jucătorului şi coeficientul de energie pentru aruncarea de lasou. Pe următoarea linie se vor afla 4 numere: $Q$, $M$, $a$ şi $b$, separate prin spaţii. Urmează $M$ linii conţinând perechi $l, r$ reprezentând intervalele pentru primele $M$ întrebări citite direct din fişier.

Fişierul de intrare $chitooc.in$ ...

h2. Date de ieşire

Pentru fiecare $i ∈ [1, M]$, pe linia $i$ se va afla răspunsul la a $i$-a întrebare, adică numărul maxim de vaci care se pot strânge pe o zonă şi energia totală minimă necesară, folosind doar zone din intervalul $[l{~i~}, r{~i~}]$.
 
Iar pe următoarele linii se va afişa suma XOR a următoarelor interogări, grupate câte 100 (numărul de vaci se XOR-ează între ele, iar costurile se XOR-ează între ele).
 
De exemplu, dacă $M = 50$ şi $Q = 400$, se va afişa individual răspunsul la primele 50 de interogări, apoi câte o pereche de răspunsuri pentru query-urile din intervalele $[51, 150]$, $[151, 250]$, $[251, 350]$, $[351, 400]$.
 
Practic, dacă răspunsurile normale ar fi formate din perechile $(val{~i~}, cost{~i~})$, unde $i ∈ [1, Q]$, $val{~i~}$ este numărul maxim de vaci, iar $cost{~i~}$ este energia minimă necesară (calculată pe baza coeficienţilor), atunci:
* pentru $i ∈ [1, M]$, se vor afişa $(val{~i~}, cost{~i~})$ pe fiecare linie;
* pentru restul întrebărilor se vor calcula şi afişa perechile $(sum_xor_val{~p~}, sum_xor_cost{~p~})$, cu $p ≥ 1$, astfel încât:
 
<tex>
\[
\text{sum\_xor\_val}_p =
\bigoplus_{i = M + (p-1)\cdot 100 + 1}^{\min(M + p \cdot 100,\, Q)} val_i
\] \
\[
\text{sum\_xor\_cost}_p =
\bigoplus_{i = M + (p-1)\cdot 100 + 1}^{\min(M + p \cdot 100,\, Q)} cost_i
\]
</tex>

În fişierul de ieşire $chitooc.out$ ...

h2. Restricţii

* $1 ≤ K ≤ N ≤ 3 * 10^5^$
* $1 ≤ Q ≤ 8 * 10^6^$
* $1 ≤ M ≤ min(Q, 10 000)$
* $0 ≤ a, b ≤ 1 000 000 000$
* $0 ≤ A_i ≤ 10^9^$
* $1 &le; pos{~1~} < pos{~2~} < ... < pos{~K~} &le; N$
* $0 &le; coef{~i~} &le; 10^9^$, pentru $i = 1, ... , K$.
* $1 &le; l &le; r &le; N$
 
table(example). |_. # |_. Punctaj |_. Restricţii |
| $1$ | $7$ | $N, Q &le; 200$|
| $2$ | $24$ | $N * Q &le; 10^6^$|
| $3$ | $5$ | $K * Q &le; 10^6^$|
| $4$ | $45$ | $N, Q &le; 10^5^$ |
| $5$ | $19$ | Fără alte restricţii |

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. chitooc.in |_. chitooc.out |

| 9 4
2 8 3 0 1 1 4 9 10
1 2
3 3
6 1
7 5
3 3 1 1
1 9
4 7
8 9
| 16 11
6 6
10 0
|
| 10 4
1 5 1 7 2 5 4 1 8 2
2 9
3 2
4 3
5 6
10 2 834673673 923993984
3 3
4 6
| 1 0
9 6
30 20
|

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

h3. Explicaţie

Pentru primul exemplu: pentru a obţine valoarea maximă şi costul minim o să avem următoarele acţiuni:
 
Pentru prima întrebare:
 
* jucătorul 2 trage vacile de pe poziţia 2;
* jucătorul 3 trage vacile de pe poziţia 3;
* jucătorul 4 trage vacile de pe poziţia 6.
 
Pentru a doua întrebare:
 
* jucătorul 3 trage vacile de pe poziţia 5;
* jucătorul 4 trage vacile de pe poziţia 6.
 
Pentru a treia întrebare:
 
* jucătorii nu o să facă nimic, iar numărul maxim de vaci o să fie 10.

...

== include(page="template/taskfooter" task_id="chitooc") ==