Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | sumzero.in, sumzero.out | Sursă | RMI 2020 Ziua 2 |
| Autor | Alexandru Petrescu | Adăugată de |  Udristoiu Alexandra Maria •alexandra_udristoiu |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Sumzero
Roxy, călătoarea spaţială, se confruntă cu o problemă foarte abstractă. Întrucât nu are idee cum să o rezolve, tu, ca prieten al ei cel mai bun, trebuie să o ajuţi.
Ea primeşte un vector c1, c2, ..., cN ce conţine N numere întregi şi Q perechi de puncte finale (Li, Ri), fiecare reprezentând subsvectorul cLi, cLi+1, ...., cRi, unde 1 ≤ i ≤ Q.
Pentru fiecare pereche (Li, Ri), Roxy este întrebată care este numărul maxim de subsecvenţe disjuncte de sumă 0 pe care le poate alege din subvectorul cLi, cLi+1, ...., cRi. Două subsecveţe sunt considerate disjuncte dacă nu au elemente în comun; cu toate acestea, pot avea puncte finale învecinate. Reţineţi că pot exista elemente din vectorul interogat care nu fac parte din niciuna din subsecvenţele alese.
Date de intrare
Fişierul de intrare sumzero.in conţine pe prima linie un singur număr întreg N.
A doua linie conţine N numere separate prin spaţii c1, c2, ..., cN.
A treia linie conţine numărul de întrebări Q.
Următoarele Q linii conţin câte două numere Li şi Ri, reprezentând a i-a întrebare.
Date de ieşire
În fişierul de ieşire sumzero.out se vor afişa Q linii, linia i conţinând răspunsul la întrebarea cu numărul i.
Restricţii
- 1 ≤ N ≤ 400 000
Exemplu
| sumzero.in | sumzero.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
