Baraj I – Juniori
Problema 3 - PP 100 puncte
Se consideră un şir de N numere naturale nenule ordonate crescător a1≤a2≤…≤aN. În legătură cu acest şir de numere ne interesează perechile de poziţii (i,j) cu 1≤i şi ai≠aj sau ne interesează suma elementelor anumitor secvențe.
Cerinţă
Se cere să se scrie un program care să citească un număr C reprezentând tipul cerinţei, un şir de N numere naturale nenule ordonate crescător a1≤a2≤…≤aN şi T perechi de numere naturale (pk,qk) cu 1≤pkk≤N şi 1≤k≤T şi apoi:
(1) Dacă C=1, atunci trebuie să se determine pentru fiecare pereche dată de numere naturale (p,q) suma ap+ap+1+…+aq.
(2) Dacă C=2, atunci trebuie să se determine pentru fiecare pereche dată de numere naturale (p,q) numărul de perechi (i,j) care respectă simultan condiţiile p≤ii≠aj.
Date de intrare
Fişierul de intrare pp.in conţine pe primul rând numărul natural C. Pe al doilea rând se află numărul N. Pe al treilea rând sunt scrise N numere naturale ordonate crescător şi separate prin câte un spaţiu. Pe al patrulea rând este scris numărul natural T, iar pe fiecare dintre următoarele T rânduri câte două numere naturale separate prin câte un spaţiu.
Date de ieşire
Dacă C=1, atunci fişierul de ieşire pp.out va conţine pe fiecare dintre primele T linii câte un număr natural. Al k-lea număr va reprezenta suma elementelor cuprinse între poziţiile pk şi qk inclusiv.
Dacă C=2, atunci fişierul de ieşire pp.out va conţine pe fiecare dintre primele T linii câte un număr natural. Al k-lea număr va reprezenta numărul cerut de perechi de indici cuprinși între poziţiile pk şi qk inclusiv.
Restricţii şi precizări
-
1 ≤ pi < qi ≤ N ≤ 100 000
-
1 ≤ a1 ≤ a2 ≤ … ≤ aN ≤ 100 000
-
1 ≤ T ≤ 1000
Exemplu:
pp.in
|
pp.out
|
Explicaţie
|
1
5
1 2 3 3 3
2
1 4
2 5
|
9
11
|
Suntem în cazul C=1. Prima pereche (p,q) este (1,4). Suma valorilor din secvență este 1+2+3+3=9. A doua pereche (p,q) este (2,5). Suma valorilor din secvență este 2+3+3+3=11.
|
2
5
1 2 3 3 3
2
1 4
2 5
|
5
3
|
Suntem în cazul C=2. Prima pereche (p,q) este (1,4). Perechile de poziţii care conţin numere diferite între ele sunt (1,2), (1,3), (1,4), (2,3), (2,4). Deci sunt 5 perechi.
A doua pereche (p,q) este (2,5). Perechile de poziţii care conţin numere diferite sunt (2,3), (2,4), (2,5). Deci sunt 3 perechi.
|
Limită de timp: 0.1 secunde
Memorie totală: 128 MB
Dostları ilə paylaş: |