LearnToCP
Prijavi se
Navigacija
PočetnaRoad-mapaProblemiO Nama
Teorija
Takmičarsko Znanje
Izbor Radnog Okruženja (IDE)
Osnove
Tvoj Prvi ProgramTipovi podataka, Unos i IzlazC++ sintaksaModuloFunkcijeVektoriMatriceVremenska Složenost Algoritma
Sortiranje
SortiranjeSortiranje PrebrojavanjemRadix Sort
Tehnike Optimizacije
Dva PokazivačaZbir brojeva od 1 do nZbir PrefiksaBinarna PretragaPohlepni AlgoritmiFunkcije Binarne PretrageBinarna Pretraga po RešenjuPodeli, pa Vladaj
Binarni Brojevi
Binarni BrojeviBrojevi u koduOperacije nad BitovimaBitmaske
Matematika
Binarno StepenovanjeProsti BrojeviRastavljanje na proste činioceNZD i NZSEratostenovo SitoModifikovano Sito
Strukture Podataka
Niske (Stringovi)StekRedMapeSkupovi (Set)Red sa PrioritetomKorišćenje Proizvoljnih KriterijumaSegmentna StablaFenvikova StablaSparse TabeleDisjunktni Skupovi
Kombinatorika
Pravilo SabiranjaPravilo MnoženjaKombinatorni ObjektiPrincip Uključenja Isključenja
Geometrija
Osnove GeometrijeVektoriVektorski i Skalarni ProizvodLinijePoligoniUgloviTačka u PoligonuRastojanja i Tačke PresekaKonveksni OmotačKrugovi
Rekurzija
PokazivačiRekurzijaGenerisanje Kombinatornih Objekata
Dinamičko Programiranje
O DP-uDP nad StablimaDP nad BitmaskamaDP nad brojevima
Teorija Grafova
GrafoviDFS i BFSNajkraći PuteviStablaTopološko SortiranjeDajkstrin AlgoritamMinimalna Razapinjuća StablaAlgoritmi Najkraćih Puteva
Napredna Teorija Grafova
Dvostruka PovezanostJako Povezane KomponenteBipartitni GrafMaksimalni Protok u GrafuFord-Fulkersonov AlgoritamDualnost Protoka i Minimalnog PresekaTeško-Laka DekompozicijaCentroidna Dekompozicija
Napredne Strukture Podataka
2D i 3D Segmentna StablaLenjo PropagiranjeImplicitna Segmentna StablaPerzistentna Segmentna StablaNajbliži Zajednički PredakTrieBalansirana Binarna Stabla PretrageMoov Algoritam

Razlika visina

EasyProblem #20
VremeMemorijaUlazIzlaz
1 s64 MBstdinstdout

Pazi na veličinu rezultata.

U jednom odeljenju biraju se glumci za školsku predstavu "Stanlio i Olio" - komičarski dvojac čuven po velikoj razlici u visini. Poznate su visine svih n učenika, a dvojac izgleda kako treba tačno kada je razlika u visini njegova dva člana tačno r.

Tvoj zadatak je da izbrojiš na koliko načina mogu da se izaberu dva učenika tako da im razlika u visini bude tačno r. Dva učenika jednakih visina su i dalje dva različita učenika - parovi se broje po tome ko je u njima, a ne po visinama.

Ulaz

U prvoj liniji je jedan ceo broj t - broj test primera.

  • U prvoj liniji svakog test primera su dva cela broja n i r - broj učenika i tražena razlika visina.
  • U sledećoj liniji je n celih brojeva a0​,a1​,…,an−1​ - visine učenika u milimetrima. Visine mogu da se ponavljaju.

Izlaz

Za svaki test primer ispiši u posebnoj liniji broj parova učenika čija je razlika visina tačno r.

Primer

Input
2
5 2350
15745 18095 15745 16234 13395
4 1
7 7 8 9
Output
4
3

U prvom test primeru parovi su: prvi i drugi učenik, prvi i peti, drugi i treći, i treći i peti. U drugom test primeru oba učenika visine 7 se uparuju sa onim visine 8, a onaj visine 8 sa onim visine 9.

Ograničenja

1≤t≤1000
1≤n≤2⋅105
1≤ai​≤109
1≤r≤109
n1​+n2​+…+nt​≤2⋅105


Zadatak je, uz dozvolu, preuzet iz zadatka Razlika visina, čiji su autori Društvo matematičara Srbije i Fondacija Petlja.

Pošalji svoje rešenje

Prijavi se da pošalješ rešenje i pratiš svoj napredak.

Prijavi se