| Fişierul intrare/ieşire: | chitooc.in, chitooc.out | Sursă | ONI 2026, Baraj Seniori, ziua 2 |
| Autor | Andrei-Cristian Turcu, Eugenie Daniel Posdarascu, Vlad-Mihai Bogdan | Adăugată de |  Ivan Andrei •IvanAndrei |
| Timp execuţie pe test | 2.5 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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 posi, el poate să adune toate vacile dintr-o zonă j în zona posi, cu condiţia ca j < posi.
- Totuşi, această mişcare consumă energia jucătorului respectiv. Dacă coeficientul energiei jucătorului este coefi, mişcarea va consuma coefi * (posi - j) unităţi de energie.
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].
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 ≤ 10 000). Restul întrebărilor, de la M + 1 până la Q, se vor genera în programul vostru folosind următorul algoritm:
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 pentruNotă: Operaţia logică pe biţi „XOR / SAU exclusiv” este reprezentată de simbolul ^ şi se efectuează în C/C++ prin operatorul ^. 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.
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.
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 [li, ri].
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 (vali, costi), unde i ∈ [1, Q], vali este numărul maxim de vaci, iar costi este energia minimă necesară (calculată pe baza coeficienţilor), atunci:
* pentru i ∈ [1, M], se vor afişa (vali, costi) pe fiecare linie;
* pentru restul întrebărilor se vor calcula şi afişa perechile (sum_xor_valp, sum_xor_costp), cu p ≥ 1, astfel încât:
![\[
\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
\]](http://www.infoarena.ro/static/images/latex/f999e902259ad182fd737adc0b0f4668_6.15549pt.gif "\[
\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
\]")
Restricţii
- 1 ≤ K ≤ N ≤ 3 * 105
- 1 ≤ Q ≤ 8 * 106
- 1 ≤ M ≤ min(Q, 10 000)
- 0 ≤ a, b ≤ 1 000 000 000
- 0 ≤ A_i ≤ 109
- 1 ≤ pos1 < pos2 < ... < posK ≤ N
- 0 ≤ coefi ≤ 109, pentru i = 1, ... , K.
- 1 ≤ l ≤ r ≤ N
| # | Punctaj | Restricţii |
|---|---|---|
| 1 | 7 | N, Q ≤ 200 |
| 2 | 24 | N * Q ≤ 106 |
| 3 | 5 | K * Q ≤ 106 |
| 4 | 45 | N, Q ≤ 105 |
| 5 | 19 | Fără alte restricţii |
Exemplu
| 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 |
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.
