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

Provera bar-kodova

Super EasyProblem #17
VremeMemorijaUlazIzlaz
1 s64 MBstdinstdout

Prodavnički spisak je već sortiran - iskoristi to.

U prodavnici se prodaje puno vrsta proizvoda i njihovi bar-kodovi su poznati, dati kao sortiran spisak. Proizvođač dostavlja spisak bar-kodova svojih proizvoda, bez posebnog redosleda. Tvoj zadatak je da odrediš koliko se proizvoda tog proizvođača već prodaje u prodavnici.

Ulaz

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

  • U prvoj liniji svakog test primera su dva cela broja n i q - broj proizvoda u prodavnici i broj proizvođačevih proizvoda.
  • U sledećoj liniji je n celih brojeva u rastućem redosledu - bar-kodovi proizvoda u prodavnici.
  • U sledećoj liniji je q celih brojeva - bar-kodovi proizvođačevih proizvoda.

Izlaz

Za svaki test primer ispiši u posebnoj liniji broj proizvođačevih bar-kodova koji se nalaze na spisku prodavnice.

Primer

Input
1
5 5
1 3 5 6 7
2 3 4 5 8
Output
2

Od proizvođačevih bar-kodova, samo se 3 i 5 nalaze na spisku prodavnice.

Ograničenja

1≤t≤1000
1≤n,q≤2⋅105
1≤ai​≤109
I zbir svih n i zbir svih q po test primerima su najviše 2⋅105.


Zadatak je, uz dozvolu, preuzet iz zadatka Provera bar-kodova, č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