Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | suma6.in, suma6.out | Sursă | Concursul Naţional de Informatică Urmaşii lui Moisil 2017 |
| Autor | Cristian Vintur | Adăugată de |  Andrici Cezar •andrici_cezar |
| Timp execuţie pe test | 2.5 sec | Limită de memorie | 128000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Suma6
Se dau două numere naturale N şi S şi un şir de N numere naturale a 1, a 2 ... a N.
Cerinţă
Să se răspundă la Q query-uri de tipul (L,R), pentru fiecare query precizând numărul de perechi (i,j), L ≤ i < j ≤ R cu proprietatea a i + a j = S.
Date de intrare
Fişierul de intrare suma6.in conţine pe prima linie numerele naturale N şi S. Pe a 2-a linie se află valorile a 1, a 2 ... a N separate prin exact un spaţiu. Linia a 3-a conţine Q, numărul de query-uri iar pe fiecare dintre următoarele Q linii, se află două numere L R separate printr-un spaţiu, corespunzătoare unui query.
Date de ieşire
Fişierul de ieşire suma.out va conţine Q linii, pe linia i va fi răspunsul pentru al i-lea query.
Restricţii
- 2 ≤ N ≤ 100.000
- 1 ≤ Q ≤ 200.000
- 0 ≤ a i ≤ 1.000.000, 1 ≤ i ≤ N
- 1 ≤ L ≤ R ≤ N
- 0 ≤ S ≤ 1.000.000
Exemplu
| suma6.in | suma6.out |
|---|---|
| 10 10 1 4 8 9 6 1 10 4 12 1 5 1 4 1 10 5 6 4 6 1 6 | 1 5 0 1 3 |
Explicaţie
De exemplu, pentru ultimul query 1 6, cele 3 perechi sunt: a 1 + a 4 = 10; a 2 + a 5 = 10; a 4 + a 6 = 10.
