Fişierul intrare/ieşire:infinitywar.in, infinitywar.outSursăRMI 2015
AutorCatalin FrancuAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test1.2 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Infinitywar

În urma evenimentelor petrecute în New York, cele N lumi ale universului Marvel se află în război. Lumea i (1 ≤ i ≤ N) este reprezentată, în acest război final, de o armată alcătuită din Ki soldaţi (posibil zero). Fiecare soldat are o singură super putere reprezentată de un număr pozitiv întreg (între 1 şi P). Puterile tuturor soldaţilor în cadrul unei armate sunt diferite.

S-a observat că, în bătălie directă, doi soldaţi se vor anihila dacă şi numai dacă cei doi au aceeaşi putere. Spre exemplu, dacă o armată formată din soldaţii cu puterile {1, 3, 5} se luptă cu armată {2, 3, 6}, atunci soldaţii care rămân în viaţă la finalul bătăliei sunt: {1, 2, 5, 6}.

Cele N lumi sunt aranjate secvenţial: prima lume are indexul 1, în timp ce ultima are indexul N.

Cerinţă

Thanos este destul că sigur că poate câştiga războiul şi distruge universul, însă doreşte să se distreze în timp ce face asta. Aşadar, el a pregătit Q întrebări. Pentru fiecare întrebare se dau doi indici x şi y şi trebuie găsit numărul de soldaţi care ar supravieţui bătăliei dintre armatele cu indicii x, x+1, x+2, ..., y.

Date de intrare

Prima linie a fişierului de input infinitywar.în conţine două numere întregi N şi Q.

Următoarele N linii conţin descrieri ale armatelor. Linia i+1 conţine un număr Ki urmat de K numere (numărul puterii fiecărui soldat).

Următoarele Q linii conţin câte două numere x şi y, separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire infinitywar.out trebuie să conţină Q linii. Fiecare linie trebuie să conţină un singur număr, raspunul pentru întrebarea corespunzătoare.

Restricţii

  • 1 ≤ N ≤ 50.000
  • 1 ≤ P ≤ 10.000
  • 1 ≤ Q ≤ 100.000
  • K1 + K2 + ... + KN ≤ 300.000
  • 1 ≤ x ≤ y ≤ N pentru fiecare întrebare.
  • Pentru 30% dintre teste N ≤ 10.000, P ≤ 500 şi Q ≤ 10.000
  • Pentru alte 40% dintre teste P ≤ 5.000 şi Q ≤ 30.000

Exemplu

infinitywar.ininfinitywar.out
4 3
2 1 2
3 1 3 97
2 1 341
5 4 2 981 341 97
1 3
2 4
1 4
5
4
4
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?