Fişierul intrare/ieşire:suma6.in, suma6.outSursăConcursul Naţional de Informatică Urmaşii lui Moisil 2017
AutorCristian VinturAdăugată deandrici_cezarAndrici Cezar andrici_cezar
Timp execuţie pe test2.5 secLimită de memorie128000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Suma6

Se dau două numere naturale N şi S şi un şir de N numere naturale a1, a2 ... aN.

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 ai + aj = 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 a1, a2 ... aN 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 ≤ ai ≤ 1.000.000, 1 ≤ i ≤ N
  • 1 ≤ L ≤ R ≤ N
  • 0 ≤ S ≤ 1.000.000

Exemplu

suma6.insuma6.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: a1 + a4 = 10; a2 + a5 = 10; a4 + a6 = 10.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?