Problem:


Search II

You are given a sequence of n integers S and a sequence of different q integers T. Write a program which outputs C, the number of integers in T which are also in the set S.

Input

In the first line n is given. In the second line, n integers are given. In the third line q is given. Then, in the fourth line, q integers are given.

Output

Print C in a line.

Constraints

Elements in S is sorted in ascending order

n ≤ 100000

 q ≤ 50000 

0 ≤ an element in S ≤ 109

0 ≤ an element in T ≤ 109

Sample Input 1

5
1 2 3 4 5
3
3 4 1

Sample Output 1

3

Sample Input 2

3
1 2 3
1
5

Sample Output 2

0

Sample Input 3

5
1 1 2 2 3
2
1 2

Sample Output 3

2

Notes

Template in C
-->



Sample input:
5
1 2 3 4 5
3
3 4 1


Sample output:
3

Submission status: Accepted

Solution code:
n = int(input())
s = input().split()
for i, x in enumerate(s):
    s[i] = int(x)
q = int(input())
t = input().split()
for i, x in enumerate(t):
    t[i] = int(x)

c = 0
len_s = len(s)
for x in t:
    l = 0
    r = len_s
    while l < r:
        if s[(l + r) // 2] == x:
            c += 1
            break
        elif s[(l + r) // 2] < x:
            l = (l + r) // 2 + 1
        else:
            r = (l + r) // 2

print(c)

Submission status: Accepted

Solution code:
def binary_search(key):
    left = 0; right = n
    cnt = 0
    while left < right:
        mid = (left + right) // 2
        if key == S[mid]:
            cnt += 1
            break
        elif key < S[mid]:
            right = mid
        else:
            left = mid + 1
    return cnt

n = int(input())
S = [int(e) for e in input().split()]
q = int(input())
T = [int(e) for e in input().split()]
cnt = 0
for key in T:
    cnt += binary_search(key)
print(cnt)

Submission status: Accepted

Solution code:
def main():
    n = int(stdinput())
    S = [*map(int, stdinput().split())]
    q = int(stdinput())
    T = [*map(int, stdinput().split())]

    S = sorted(S)

    c = 0
    for t in T:
        if binary_search(S, len(S), t):
            c += 1
    
    print(c)

def binary_search(S, n, t):
    left = 0
    right = n - 1
    
    # print(*S)

    while left <= right:
        mid = (left + right) // 2

        # print(*[t, left, right, mid])
        # print(*[t, S[mid]])
        
        if S[mid] == t:
            return True
        elif S[mid] > t:
            right = mid - 1
        else:
            left = mid + 1
    
    return False

def stdinput():
    from sys import stdin
    return stdin.readline().strip()

if __name__ == '__main__':
    main()
    # import cProfile
    # cProfile.run('main()')

Submission status: Accepted

Solution code:
n = int(input())
s = [int(i) for i in input().split()]
q = int(input())
t = [int(i) for i in input().split()]
ans = 0
s.append(10000000000)
for i in range(q):
    l = 0
    r = n + 1
    while r - l > 1:
        m = (l + r) // 2
        if s[m] > t[i]:
            r = m
        else:
            l = m
    if r > 0 and s[r - 1] == t[i]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
S=[int(i) for i in input().split()]
q=int(input())
T=[int(i) for i in input().split()]
s=0
S.append(10**10)
for i in range(q):
    l=0
    r=n+1
    while r-l>1:
        m=(l+r)//2
        if S[m]>T[i]:
            r=m
        else:
            l=m
    if S[l]==T[i]:
        s+=1    
print(s)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = sorted([int(_) for _ in input().split()])
    Q = int(input())
    T = sorted([int(_) for _ in input().split()])

    ans = 0

    for t in T:
        left = 0
        right = len(S) - 1

        while True:
            mid = (left + right) // 2
            if S[mid] == t:
                ans += 1
                break
            elif S[mid] < t:
                left = mid + 1
            else:
                right = mid - 1

            if left > right:
                break

    print(ans)

main()

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int, input().split()))
q = int(input())
t = list(map(int, input().split()))
count = 0
for a in t:
    left = 0
    right = n
    while left < right:
        mid = (right + left) // 2
        if a == s[mid]:
            count += 1
            break
        elif a < s[mid]:
            right = mid
        else :
            left = mid + 1

print(count)

Submission status: Accepted

Solution code:
def binarySearch(key, arr, N):
    left = 0
    right = N
    while left < right:
        mid = (left + right) // 2
        if arr[mid] == key:
            return 1
        elif key < arr[mid]:
            right = mid
        else:
            left = mid + 1
    return 0


N1 = int(input())
arr1 = [int(n) for n in input().split()]
N2 = int(input())
arr2 = [int(n) for n in input().split()]

print(sum([binarySearch(key, arr1, N1) for key in arr2]))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n=int(input())
S=list(map(int,input().split()))
S1=set(S)


q=int(input())
T=list(map(int,input().split()))
count=0

for j in range(q):
    if T[j] in S1:
        count+=1
    
        
print(count)

Submission status: Accepted

Solution code:
import math
a = int(input())
listA = list(map(int, input().split()))

b = int(input())
listB = list(map(int, input().split()))

count = 0
for i in range(b):
    key = listB[i]
    left = 0
    right = a
    while left < right:
        mid = math.floor((left+right)/2)
        if listA[mid] == key:
            count += 1
            break
        elif key < listA[mid]:
            right = mid
        else:
            left = mid + 1

print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

input()
s = set(input().split())
input()
t = set(input().split())
print(len(s & t))

Submission status: Accepted

Solution code:
N = int(input())
L = input().split()
L = [int(s) for s in L]
n = int(input())
l = input().split()
l = [int(s) for s in l]
ans = 0
for i in range(n):
    j = 0
    k = N-1
    while(1):
    #for m in range(5):
        a =  int((j + k)/2)
        if l[i] == L[a] or l[i] ==L[j] or l[i] ==L[k]:
            ans += 1
            break
        elif k == j+1:
            break
        elif l[i] > L[a]:
            j = a
        elif l[i] < L[a]:
            k = a
        # print(j,k,a,ans)
        # print(l[i],L[a])
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

n = int(input())
S = [int(t) for t in input().split()]
q = int(input())
T = [int(t) for t in input().split()]
assert n == len(S) and q == len(T)

def isin(t, S):
    i = bisect_left(S, t)
    return i < len(S) and S[i] == t

print(sum(1 for t in T if isin(t, S)))

Submission status: Accepted

Solution code:
# AOJ ALDS1_4_B Binary Search
# Python3 2018.7.3 bal4u

n = int(input())
s = set(map(int, input().split()))
q = int(input())
t = set(map(int, input().split()))
print(len(s & t))

Submission status: Accepted

Solution code:
# AOJ ALDS1_4_B Binary Search
# Python3 2018.7.3 bal4u

import sys
from sys import stdin
input = stdin.readline

n = int(input())
s = set(map(int, input().split()))
q = int(input())
t = set(map(int, input().split()))
print(len(s & t))

Submission status: Accepted

Solution code:
# AOJ ALDS1_4_B Binary Search
# Python3 2018.7.3 bal4u

n = input()
s = set(input().split())
q = input()
t = set(input().split())
print(len(s & t))

Submission status: Accepted

Solution code:
n = int(input())
S =list(map(int,input().split(" ")))
l =int(input())
T =list(map(int,input().split(" ")))
ans =0
for t in T:
    left=0
    right=n
    while left < right:
        mid=(left+right)//2
        if  S[mid] == t:
           ans+=1
           break
        elif S[mid] > t:
            right = mid
        else:
            left = mid +1
print(ans)

Submission status: Accepted

Solution code:
def f():
    return raw_input()
def f2():
    return set(raw_input().split())

n = f()
S = f2()
q = f()
T = f2()

print len(S & T)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
stdin.readline()
s = {int(s) for s in stdin.readline().split()}
stdin.readline()
s.intersection_update((int(s) for s in stdin.readline().split()))
print(len(s))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding:utf-8 -*-
#from __future__ import print_function
import time
import sys
import io
import re
import math
start = time.clock()
i = 0
n=input()
S=map(int, raw_input().split())
q=input()
T=map(int, raw_input().split())
#s=sorted(set(S), key=S.index)
print len(set(S)&set(T))

Submission status: Accepted

Solution code:
n = int(raw_input())
T = set(map(int, raw_input().split()))
n = int(raw_input())
S = set(map(int, raw_input().split()))
print len(T&S)

Submission status: Accepted

Solution code:
n = int(raw_input())
T = set(raw_input().split())
n = int(raw_input())
S = set(raw_input().split())
print len(T&S)

Submission status: Accepted

Solution code:
a = [raw_input() for i in range(4)]
print len(set(a[1].split())&set(a[3].split()))

Submission status: Accepted

Solution code:
n1 = int(input())
s1 = set(map(int, input().strip().split()))
n2 = int(input())
s2 = set(map(int, input().strip().split()))
print(len(s1 & s2))

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int,input().split()))
q = int(input())
T = list(map(int,input().split()))
ans = 0
def binary_search(lis,item):
    l = 0
    r = len(lis) - 1
    while l <= r:
        mid = (l+r)//2
        guess = lis[mid]
        if guess == item:
            return 1
        if guess > item:
            r = mid -1
        else:
            l = mid + 1
    return 0
for i in T:
    ans += binary_search(S,i)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
S=list(map(int,input().split()))
q=int(input())
T=list(map(int,input().split()))

import bisect
ans=0

for t in T:
    b=bisect.bisect(S,t)
    #print(b)
    if b!=0 and t==S[b-1]:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
num1 = int(input())
a1 = list(map(int,input().split()))

num2 = int(input())
a2 = list(map(int,input().split()))

count = 0

for i in range(num2):
    left = 0
    right = num1
    
    while left < right:
        mid = int((left + right) /2)
        
        if a1[mid] == a2[i]:
            count +=1
            break
        
        elif a2[i] < a1[mid]:
            right = mid
        else:
            left = mid +1
        

print(count)

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
c = 0


def BinarySearch(A, key):
    left = 0
    right = n
    while left < right:
        mid = (left+right)//2
        if A[mid] == key:
            return 1
        elif key < A[mid]:
            right = mid
        else:
            left = mid+1
    return 0


for i in T:
    if (BinarySearch(S, i)):
        c += 1

print(c)

Submission status: Accepted

Solution code:
def bisearch(x,L):
    left = 0
    right = len(L)
    
    while left < right:
        mid = (left+right)//2
        
        if L[mid] == x:
            return True
        elif L[mid] > x:
            right = mid
        else:
            left = mid + 1
    
    return False
    

n = int(input())
S = list(map(int,input().split()))
q = int(input())
T = list(map(int,input().split()))

ans = 0
for x in T:
    judge = bisearch(x,S)
    if judge == True:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=list(map(int,input().split()))
q=int(input())
t=list(map(int,input().split()))
ans=0

for i in range(q):
  left=0
  right=n
  while left<right:
    mid=(left+right)//2
    if s[mid]==t[i]:
      ans+=1
      break
    elif t[i]<s[mid]:
      right=mid
    else:
      left=mid+1
print(ans)

Submission status: Accepted

Solution code:
def binary_search(a, tgt):
    low = 0
    high = len(a) - 1
    while low <= high:
        mid = (low + high) // 2
        cand = a[mid]
        
        if cand == tgt:
            return mid
        if cand > tgt:
            high = mid - 1
        else:
            low = mid + 1
    
    return -1

n = int(input())
s = list(map(int, input().split()))
q = int(input())
t = list(map(int, input().split()))

cnt = 0
for tgt in t:
    flag = binary_search(s, tgt)
    if flag >= 0:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
S_L = list(map(int, input().split()))
Q = int(input())
T_L = list(map(int, input().split()))


def bisect(a_l, x):
    _l = 0
    _r = len(a_l)-1
    while _r - _l > 1:
        _c = (_l + _r)//2
        _tmp = a_l[_c]
        if _tmp == x:
            return _c
        elif _tmp > x:
            _r = _c
        else:
            _l = _c
    if a_l[_l] == x:
        return _l
    elif a_l[_r] == x:
        return _r
    else:
        return False


ans = 0
for i in range(Q):
    if bisect(S_L, T_L[i]) is not False:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = list(map(int, input().split()))
Q = int(input())
T = list(map(int, input().split()))

def binary_search(S, key):
    left = 0
    right = N
    while left < right:
        mid = (left + right) // 2
        if S[mid] < key:
            left = mid + 1
        elif S[mid] > key:
            right = mid
        else:
            return True
    return False
cnt = 0
for t in T:
    if binary_search(S, t):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

n = I()
S = LI()
q = I()
T = LI()
ans = 0
for t in T:
    a = 0
    for i in range(1, 10 * math.ceil(math.log(2, n)) + 10):
        if S[a] == t:
            ans += 1
            break
        elif S[a] < t:
            a += math.ceil(n / pow(2, i))
            if a >= n - 1:
                a = n - 1
        else:
            a -= math.ceil(n / pow(2, i))
            if a <= 0:
                a = 0
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

def BinarySearch(x):
    l, r = 0, n
    while l < r:
        mid = (l + r) // 2
        a = x - S[mid]
        if a == 0:
            return True
        elif a > 0:
            l = mid + 1
        elif a < 0:
            r = mid
    return False

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

cnt = 0
for x in T:
    if BinarySearch(x):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

def binarySearch(A, key, n):
    left = 0
    right = n
    while left < right:
        mid = (left + right) // 2
        if A[mid] == key:
            return 1
        elif key < A[mid]:
            right = mid
        else:
            left = mid + 1
    return 0

C = 0
for t in T:
    if binarySearch(S, t, n):
        C += 1
print(C)

Submission status: Accepted

Solution code:
def binary_search(A, n, key):
    left = 0
    right = n
    while left < right:
        mid = int((left + right) / 2)
        if key == A[mid]:
            return True
        elif key > A[mid]:
            left = mid + 1
        elif key < A[mid]:
            right = mid
    return False

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

ans = 0
for t in T:
    if binary_search(S, n, t):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

C = 0

for t in T:
    index = bisect.bisect_left(S, t)
    if index < n and S[index] == t:
        C += 1
print(C)

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))


def binarySearch(data, value):
    left = 0
    right = len(data) - 1
    while left <= right:
        mid = (left + right) // 2
        if data[mid] == value:
            return mid
        elif data[mid] < value:
            left = mid + 1
        else:
            right = mid - 1
    return -1


ans = []
for j in range(q):
    if binarySearch(S, T[j]) > -1:
        ans.append(binarySearch(S, T[j]))
print(len(ans))

Submission status: Accepted

Solution code:
def binary_search(n, S, T):
    count = 0
    for t in T:
        left = 0
        right = n
        while left <= right:
            middle = (left + right)//2
            center = S[middle]
            if t == center:
                count += 1
                break
            elif t < center:
                right = middle - 1
            else:
                left = middle + 1
    return count


def main():
    n = int(input())
    S = list(map(int, input().split()))
    q = int(input())
    T = list(map(int, input().split()))

    print(binary_search(n, S, T))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
_, s, _, t = [set(o.split()) for o in open(0)]
print(len(s & t))

Submission status: Accepted

Solution code:
n = int(input())
S = set(map(int, input().split()))
q = int(input())
T = set(map(int, input().split()))
C = S & T
print(len(C))

Submission status: Accepted

Solution code:
n = int(input())
S = [int(i) for i in input().split()]
q = int(input())
T = [int(j) for j in input().split()]

ans = 0

def binarySearch(key,array):
    left = 0
    right = len(array)

    while left < right:
        mid = (right+left)//2

        if array[mid] == key:
            return True
        else:
            if key < array[mid]:
                right = mid
            else:
                left = mid+1

    return False


for i in range(q):
    key = T[i]

    if binarySearch(key,S):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))


count = 0
for t in T:
    bottom = 0
    top = n  
    while top - bottom > 0:
        middle = (top + bottom) // 2
        
        if t == S[middle]:
            count += 1
            break

        if t > S[middle]:
            bottom = middle + 1
        if t < S[middle]:
            top = middle

print(count)

Submission status: Accepted

Solution code:
from bisect import bisect_right as bisect

n=int(input())
s=list(map(int,input().split()))
q=int(input())
t=list(map(int,input().split()))

s.sort()

ans=0
for i in range(q):
    index=bisect(s,t[i])
    if index>0:
        if t[i]==s[index-1]:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

c = 0
for i in T:
    left = 0
    right = n
    while left < right:
        mid = (left + right)//2
        if S[mid] == i:
            c +=1
            break
        elif S[mid] > i:
            right = mid
        else:
            left = mid + 1

print(c)

Submission status: Accepted

Solution code:
def main():
    import sys
    import math

    asa =  sys.stdin.readline
    n = int(input())
    s = list(map(int, asa().split()))
    q = int(input())
    t = list(map(int, asa().split()))
    c = 0

    stopper = math.log2(n) + 1

    for i in t: # tの中のiを探索vim
        time = 0
        middle = int(n/2)
        small = 0
        large = n
        time = 0

        while s[middle] != i and time < stopper:
            if s[middle] > i:
                large = middle
                middle = int((middle + small) / 2)

            else:
                small = middle
                middle = int((middle + large) / 2)

            time += 1
        if s[middle] == i:
            c += 1

    print(c)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
_, S = input(), [*map(int, input().split())]
_, T = input(), [*map(int, input().split())]

def binary_search(S, t):
  left, right = 0, len(S)
  while left < right:
    mid = (left + right) // 2
    if S[mid] == t:
      return True
    if S[mid] > t:
      right = mid
    else:
      left = mid + 1
  return False

print(sum(binary_search(S, t) for t in T))

Submission status: Accepted

Solution code:
n=int(input())
s=list(map(int, input().split()))
s=sorted(s)
q=int(input())
t=list(map(int, input().split()))
frt=0
end=n
def src(x:list, y:int):
  frt=0
  end=len(x)-1
  while end>=frt:
    cent=(frt+end)//2
    if x[cent]==y:
      return 1
    elif x[cent]<y:
      frt=cent+1
    else:
      end=cent-1
  return 0
ans=0
for i in t:
  ans+=src(s, i)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
count = 0

for i in range(q):
    t = T[i]
    left = 0
    right = n
    while left < right:
        mid = (left + right) // 2
        if S[mid] == t:
            count += 1
            break
        elif t < S[mid]:
            right = mid
        else:
            left = mid + 1
print(count)

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int,input().split()))
q = int(input())
t = list(map(int,input().split()))

cnt = 0
for x in t:
    l = 0
    r = n
    while l<r:
        mid = (l+r)//2
        if s[mid]!=x:
            if s[mid]<x:
                l = mid + 1
            else:
                r = mid
        else:
            cnt += 1
            break
print(cnt)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n=int(input())
S=list(map(int,input().split()))
q=int(input())
T=list(map(int,input().split()))

def binarySearch(x,lst):
    left=0
    right=(len(lst))
    while left<right:
        mid=(left+right)//2
        if lst[mid]==x:
            return True
        elif x<lst[mid]:
            right=mid
        else:
            left=mid+1
    return False
a=(list(map(lambda x:binarySearch(x,S),T)))
print(a.count(True))

Submission status: Accepted

Solution code:
N=int(input())
*S,=map(int,input().split())
Q=int(input())
*T,=map(int,input().split())

# N=5
# S=[1,2,3,4,5]
# Q=3
# T=[9]

def bs(key, l):
    low=0
    high=len(l)-1 # 最大値のindexはリストの長さから1を引く
    while low<=high: # lowがhighより低い限りは処理を続ける。
        mid = (low+high)//2
        if l[mid] == key:
            return True
        elif key < l[mid]: 
            high = mid-1 # この時点でmidではないので1つずらすこと
        else:
            low = mid+1  # この時点でmidではないので1つずらすこと
    else:
        return False
cnt=0
for i in T:
    if bs(i, S):
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
def BinarySearch(A,key):
    left = 0
    right = len(A) 
    while left < right:
        mid = (left + right)//2
        if A[mid] == key:
            return True
        elif key < A[mid]:
            right = mid
        else:
            left = mid + 1
    return False


n = int(input())
S = list(map(int,input().split()))

q = int(input())
T = list(map(int,input().split()))

count = 0
for key in T:
    if BinarySearch(S,key):
        count += 1
print(count)

Submission status: Accepted

Solution code:
import sys

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))


n = inp()
S = inpl()
q = inp()
T = inpl()

S.sort()
T.sort()

# 先頭インデックスを返す
#   存在しなかった場合はどうする？
def binary_search(num):
    left = 0
    right = n-1
    while right - left > 1:
        mid = (right + left) // 2
        if S[mid] >= num:
            right = mid
        else:
            left = mid
    if S[right] == num:
        return right
    else:
        return -1

def dup_count(idx):
    for i in range(idx, n-1):
        if S[idx] == S[i]:
            pass
        else:
            break
    return i - idx + 1

ans = 0
for i in T:
    idx = binary_search(i)
    if idx >= 0:
        ans += 1
        # ans += dup_count(idx)
print(ans)

Submission status: Accepted

Solution code:
#get input
n = input()
S = list(map(lambda x: int(x), input().split(' ')))
q = input()
T = list(map(lambda x: int(x), input().split(' ')))

#iterate T and count
count = 0
for i in T:
    #binary search
    left = 0
    right = len(S)-1
    while left <= right:
        pointer = (left+right)//2
        if S[pointer] == i:
            count += 1
            break
        elif S[pointer] < i:
            left = pointer+1
        else:
            right = pointer -1
print(count)

Submission status: Accepted

Solution code:
n = int(input())
s = set(map(int, input().split()))
q = int(input())
t = set(map(int, input().split()))

print(len(s & t))

Submission status: Accepted

Solution code:
import bisect

n = int(input())
s_li = list(map(int, input().split()))
q = int(input())
t_li = list(map(int, input().split()))

def binary_search(li, item):
    low = 0
    high = len(li) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = li[mid]
        
        if guess == item:
            return mid
        
        if guess > item:
            high = mid - 1
        
        if guess < item:
            low = mid + 1
    return None

cnt = 0
for i in t_li:
    if binary_search(s_li, i) is not None:
        cnt += 1
        
print(cnt)

Submission status: Accepted

Solution code:
input()
s1 = set(input().split())
input()
s2 = set(input().split())
print(len(s1 & s2))

Submission status: Accepted

Solution code:
def bs(key):
    left = 0
    right = n
    while left < right:
        mid = (left + right) // 2
        if s[mid] == key:
            return True
        elif key < s[mid]:
            right = mid
        else:
            left = mid + 1
    return False


n = int(input())
*s, = map(int, input().split())
input()
*t, = map(int, input().split())
print(sum(bs(i) for i in t))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

# 二分探索
def binary_search(x: int) -> bool:
    low = 0
    high = len(S) - 1
    while low <= high:
        mid = (low + high) // 2
        guess = S[mid]
        if guess == x:
            return True
        if guess < x:
            low = mid + 1
        else:
            high = mid - 1
    return False

# 求解処理
ans = 0
for t in T:
    ans += binary_search(t)

# 結果出力
print(ans)

Submission status: Accepted

Solution code:
import bisect 
s=int(input())
S=list(map(int,input().split()))
t=int(input())
T=sorted(list(map(int,input().split())))
ans=0
for x in T:
    ok = bisect.bisect(S,x)-1
    if S[max(ok,0)]==x:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
s = list(map(int, input().split()))
s.sort()
q = int(input())
t = list(map(int, input().split()))

ans = 0
for num in t:
    index = bisect.bisect_left(s, num)
    # indexが超えた場合
    if index >= n:
        continue
    if num == s[index]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def binary_search(l, key):
    left = 0
    right = len(l)
    while left < right:
        mid = (left + right) // 2
        if l[mid] == key:
            return 1
        elif key < l[mid]:
            right = mid
        else:
            left = mid + 1
    return 0


n = int(input())
s = list(map(int, input().split()))
q = int(input())
t = list(map(int, input().split()))
ans = 0
for i in t:
    if binary_search(s, i) != 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))

q = int(input())
T = list(map(int, input().split()))

ans = 0
for t in T:
    left = 0
    right = n
    while left < right:
        mid = (left + right) // 2
        if S[mid] == t:
            ans += 1
            break
        elif S[mid] > t:
            right = mid
        else:
            left = mid + 1
print(ans)

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque
import copy

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    S = set(il())
    Q = ii()
    T = set(il())

    ret = 0
    for t in T:
        if t in S:
            ret += 1
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
input()
a = set(input().split())
input()
b = set(input().split())
print(len(a & b))

Submission status: Accepted

Solution code:
from bisect import bisect_left

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

ans = 0

for i in range(q):
    x = bisect_left(S, T[i])
    if x < n:
        if S[x]==T[i]:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
n1 = int(input())
nums1 = list(map(int, input().split()))
n2 = int(input())
nums2 = list(map(int, input().split()))

def binary_search(nums1, n1, key):
    L,R = 0, n1
    while L < R:
        pivot = (L + R) // 2
        if nums1[pivot] == key:
            return True

        if key > nums1[pivot]:
            L = pivot + 1
        else:
            R = pivot
    return False

output = 0
nums1.append(None)
for key in nums2:
    if binary_search(nums1, n1, key):
        output += 1

print(output)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left, bisect_right

n = int(sys.stdin.buffer.readline().rstrip())
q = list(map(int, sys.stdin.buffer.readline().split()))
s = int(sys.stdin.buffer.readline().rstrip())
t = list(map(int, sys.stdin.buffer.readline().split()))

ans = 0
for i in t:
    if q[bisect_left(q, i, 0, n-1)] == i:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int, input().split()))
q = int(input())
t = list(map(int, input().split()))

def binary_search(a, x):
    # aがxに含まれていればTrue,そうでなければFalse
    left = -1
    right = len(x)
    mid = (left + right) // 2
    if not x[0] <= a <= x[-1]:
        return False
    
    while True:
        if x[mid] == a:
            return True
        if a < x[mid]:
            right =  mid
            mid = (left + right) // 2
        else:
            left = mid
            mid = (left + right) // 2
        if right == mid or left == mid:
            return False
    return False

s.sort()
cnt = 0
for i in t:
    if binary_search(i, s):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
S.sort()
ans = 0
for t in T:
    l = -1
    r = n
    while r-l > 1:
        mid = (r+l)//2
        if S[mid] <= t:
            l = mid
        else:
            r = mid
    if l != -1 and S[l] == t:
        ans += 1
print(ans)