Fişierul intrare/ieşire:sumzero.in, sumzero.outSursăRMI 2020 Ziua 2
AutorAlexandru PetrescuAdăugată dealexandra_udristoiuUdristoiu Alexandra Maria •alexandra_udristoiu
Timp execuţie pe test0.75 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.

Restrictii

  • 1 ≤ N ≤ 400 000
  • 1 ≤ Q ≤ 400 000
  • -109 ≤ ci ≤ 109
  • 1 ≤ Li ≤ Ri ≤ N
  • Pentru 20 de puncte, 1 ≤ N, Q ≤ 5 000
  • Pentru alte 40 de puncte, 1 ≤ N, Q ≤ 100 000

Exemplu

sumzero.insumzero.out
10
1 2 -3 0 1-4 3 2 -1 1
3
1 10
1 5
2 9
4
2
2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?