Problem:

Equal Range

 

For a given sequence $A = \{a_0, a_1, ..., a_{n-1}\}$ which is sorted by ascending order, print a pair of the lower bound and the upper bound for a specific value $k$ given as a query.

  lower bound: the place pointing to the first element greater than or equal to a specific value, or $n$ if there is no such element.

  upper bound: the place pointing to the first element greater than a specific value, or $n$ if there is no such element.
  

Input

  The input is given in the following format.

$n$
$a_0 \; a_1 \; ,..., \; a_{n-1}$
$q$
$k_1$
$k_2$
:
$k_q$

The number of elements $n$ and each element $a_i$ are given in the first line and the second line respectively. In the third line, the number of queries $q$ is given and the following $q$ lines, $q$ integers $k_i$ are given as queries.

Output

  For each query, print the pari of the lower bound $l$ ($l = 0, 1, ..., n$) and upper bound $r$ ($r = 0, 1, ..., n$) separated by a space character in a line.

Constraints

  
$1 \leq n \leq 100,000$

  
$1 \leq q \leq 200,000$

  
$0 \leq a_0 \leq a_1 \leq ... \leq a_{n-1} \leq 1,000,000,000$
  
$0 \leq k_i \leq 1,000,000,000$

Sample Input 1

4
1 2 2 4
3
2
3
5

Sample Output 1

1 3
3 3
4 4



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


Sample output:
1 3
3 3
4 4

Submission status: Accepted

Solution code:

import bisect

n = int(input())
a = list(map(int, input().split(' ')))
q = int(input())
for i in range(q):
    k = int(input())
    print(bisect.bisect_left(a, k), bisect.bisect_right(a, k))

Submission status: Accepted

Solution code:

def equal_range(li, x):
    """Returns a pair of indices (lower_bound, upper_bound).

    >>> equal_range([1, 2, 2, 3], 0)
    (0, 0)
    >>> equal_range([1, 2, 2, 3], 1)
    (0, 1)
    >>> equal_range([1, 2, 2, 3], 2)
    (1, 3)
    >>> equal_range([1, 2, 2, 3], 3)
    (3, 4)
    >>> equal_range([1, 2, 2, 3], 4)
    (4, 4)
    >>> equal_range([2, 2, 2, 2], 2)
    (0, 4)
    """
    def is_lower_bound(i):
        if i == 0:
            return li[i] >= x
        elif i == len(li):
            return li[i-1] < x
        else:
            return (li[i-1] < x and li[i] >= x)

    def is_upper_bound(i):
        if i == 0:
            return li[i] > x
        elif i == len(li):
            return li[i-1] <= x
        else:
            return (li[i-1] <= x and li[i] > x)

    def find_lower(i, j):
        if i == j:
            return i
        mid = i + (j - i) // 2
        if li[mid] >= x:
            return find_lower(i, mid)
        else:
            return find_lower(mid+1, j)

    def find_upper(i, j):
        if i == j:
            return i
        mid = i + (j - i) // 2
        if li[mid] > x:
            return find_upper(i, mid)
        else:
            return find_upper(mid+1, j)

    def search(lo, hi):
        if is_lower_bound(lo) and is_upper_bound(hi):
            return (lo, hi)

        mid = lo + (hi - lo) // 2
        if li[mid] > x:
            return search(lo, mid)
        elif li[mid] < x:
            return search(mid+1, hi)
        else:
            lo = find_lower(lo, mid)
            hi = find_upper(mid+1, hi)
            return search(lo, hi)

    return search(0, len(li))


def run():
    n = int(input())
    a = [int(x) for x in input().split()]
    assert(n == len(a))

    q = int(input())
    for _ in range(q):
        k = int(input())
        x, y = equal_range(a, k)
        print("{} {}".format(x, y))


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
# AOJ ITP2_6_D: Equal Range
# Python3 2018.6.24 bal4u

from bisect import bisect_left, bisect_right
n = int(input())
a = list(map(int, input().split()))
a.append(1000000001)  # > 1,000,000,000
q = int(input())
for i in range(q):
	k = int(input())
	print(bisect_left(a, k), bisect_right(a, k))

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left
from bisect import bisect_right

input()
arr = list(map(int, input().split()))
nq = int(input())
lines = sys.stdin.readlines()

ans = [None] * nq
for i in range(nq):
    q = int(lines[i])
    ans[i] = '{} {}'.format(
        (bisect_left(arr, q)), bisect_right(arr, q))
print('\n'.join(ans))

Submission status: Accepted

Solution code:
def binaryUpper(n, a):
    ok = -1
    ng = len(a)
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        # print("n:", n, "idx:", mid, "val:", a[mid], ok, ng, file=sys.stderr)
        if a[mid] <= n:
            ok = mid
        else:
            ng = mid
    return ng


def binaryLower(n, a):
    ok = len(a)
    ng = -1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        # print("n:", n, "idx:", mid, "val:", a[mid], ok, ng, file=sys.stderr)
        if a[mid] >= n:
            ok = mid
        else:
            ng = mid
    return ok


def resolve():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = [int(i) for i in input().split()]
    q = int(input())
    for _ in range(q):
        k = int(input())
        print(binaryLower(k, a), binaryUpper(k, a))


resolve()

Submission status: Accepted

Solution code:
import bisect

input()
a = list(map(int,input().split()))

for i in range(int(input())):
    k = int(input())
    print(bisect.bisect_left(a,k),bisect.bisect(a,k))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

n = int(input())
a = [*map(int, input().split())]
q = int(input())
while q:
    q -= 1
    k = int(input())
    print(bisect_left(a, k), bisect_right(a, k))

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect
n = int(input())
a = list(map(int,input().split()))
#a.append(1000000001)
q = int(input())

for i in range(q):
    k = int(input())
    print(bisect_left(a,k),bisect(a,k))

Submission status: Accepted

Solution code:

import bisect

def main():
    n = int(input())
    A = list(map(int,input().split()))
    q = int(input())
    for _ in range(q):
        b = int(input())
        lb = bisect.bisect_left(A,b)
        ub = bisect.bisect_right(A,b)
        print (lb,ub)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
    k = int(input())
    print(bisect_left(a, k), bisect_right(a, k))

Submission status: Accepted

Solution code:
import bisect

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

for i in range(q):
    query = int(input())
    lower = bisect.bisect_left(A, query)
    upper = bisect.bisect_right(A, query)

    print("{} {}".format(lower, upper))

Submission status: Accepted

Solution code:
import bisect

def main():
    n = int(input())
    li = [int(a) for a in input().split()]
    q = int(input())

    for _ in range(q):
        k = int(input())
        l = bisect.bisect_left(li, k)
        u = bisect.bisect_right(li,k)
        print("{0} {1}".format(l, u))
main()

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    n = int(f_i.readline())
    A = list(map(int, f_i.readline().split()))
    q = int(f_i.readline())
    
    from bisect import bisect_left as bl
    from bisect import bisect_right as br
    ans = []
    for i in range(q):
        k = int(f_i.readline())
        ans.append(' '.join(map(str, (bl(A, k), br(A, k)))))
    
    print('\n'.join(ans))

solve()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left
from bisect import bisect_right

n = int(input())
a = tuple(map(int,sys.stdin.readline().split()))
q = int(input())

l = len(a)
for k in sys.stdin:
    k = int(k.strip())
    if k > a[-1]:print(l, l)
    else:
        print(bisect_left(a,k), bisect_right(a,k))

Submission status: Accepted

Solution code:
from bisect import *
input()
L = [int(x) for x in input().split()]
n = int(input())
for _ in range(n):
    x = int(input())
    print(bisect_left(L,x), bisect_left(L,x+1))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split( )))
q=int(input())
k=[]
for i in range(q):
    k1=int(input())
    k.append([k1,i])

a.sort()
k.sort()

lwb = [n]*q
upb = [n]*q

i1 = 0 #k,lowwerbound
i2 = 0 #k,upper
j1 = 0 #a,lower
j2 = 0 #a,upper

while i1<q and i2<q and j1<n and j2<n:
    try:
        while k[i1][0] > a[j1]:
            j1 += 1
    except:
        pass
    try:
        while k[i1][0] >= a[j2]:
            j2 += 1
    except:
        pass

    lwb[k[i1][1]] = j1
    i1+=1
    upb[k[i2][1]] = j2
    i2+=1

for i in range(q):
    print(lwb[i],upb[i])

Submission status: Accepted

Solution code:
from bisect import bisect


if __name__ == "__main__":
    n = int(input())
    a = list(map(lambda x: int(x), input().split()))
    num_query = int(input())

    for _ in range(num_query):
        k = int(input())
        print(f"{bisect(a, k - 1)} {bisect(a, k)}")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Binary Search - Equal Range
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_6_D&lang=jp

"""
from bisect import bisect_left, bisect_right

n = int(input())
A = [int(a) for a in input().split()]
for _ in range(int(input())):
    k = int(input())
    print(bisect_left(A, k), bisect_right(A, k))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
    k = int(input())
    print(bisect_left(a, k), bisect_right(a,k))

Submission status: Accepted

Solution code:
#binary search
import bisect

if __name__ == '__main__':

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

	for _ in range(n):
		x = int(input())
		
		bi_l = bisect.bisect_left(A,x)
		bi_r = bisect.bisect_right(A,x)
		print(bi_l,bi_r)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right



n = int(input())

A = tuple(map(int, input().split()))

q = int(input())


for _ in range(q):

    k = int(input())

    print(bisect_left(A, k), bisect_right(A, k))

Submission status: Accepted

Solution code:
from bisect import *

n = int(input())
box = list(map(int, input().split()))
q = int(input())
for _ in range(q):
    k = int(input())
    print(bisect_left(box,k),bisect(box,k))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
n = int(input())
a = list(map(int, input().split()))
a.append(1000000001)  # > 1,000,000,000
q = int(input())
for i in range(q):
    k = int(input())
    print(bisect_left(a, k), bisect_right(a, k))

Submission status: Accepted

Solution code:
import bisect

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

for i in range(q):
    k=int(input())
    print(bisect.bisect_left(A,k),bisect.bisect_right(A,k))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

n = int(input())
A = [int(x) for x in input().split()]
q = int(input())

for i in range(q):
    k = int(input())
    print(bisect_left(A, k), bisect_right(A, k))

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_6_D&lang=jp
#  Equal Range : python3
#  2018.11.26 yonezawa

import sys
input = sys.stdin.readline

def LowerBound(d,l):
    max = len(l) -1
    min = 0
    mid = max // 2
    while True:
        if (l[mid] > d ):
            max = mid
        elif (l[mid] == d ):
            while l[mid] == d and mid >= 0:
                mid -= 1
            return mid + 1
        else:
            min = mid
        mid =  (max + min ) // 2 

        if ( mid == max or mid == min ):
            if ( l[mid] == d or l[max] == d):
                while l[mid] == d and mid >= 0:
                    mid -= 1
                return mid+1
            if ( l[max] < d ):
                return len(l)
            if ( l[mid] > d):
                return min
            return max
def main():
    nl = int(input())
    l = list(map(int,input().split()))

    for i in range(int(input())):
        n = int(input())
        result1 = LowerBound(n,l)
        result2 = LowerBound(n+1,l)

        print (result1,result2)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import bisect
input()
arr = list(map(int, input().split()))
nq = int(input())
lines = sys.stdin.readlines()
ans = [None] * nq
for i in range(nq):
    q = int(lines[i])
    ans[i] = '{} {}'.format((bisect.bisect_left(arr, q)), bisect.bisect_right(arr, q))
print('\n'.join(ans))

Submission status: Accepted

Solution code:
import bisect

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

q = int(input())
for _ in range(q):

    k = int(input())
    if k > num[-1]:
        print(n, n)
        continue
    else:
        print(bisect.bisect_left(num, k), bisect.bisect_right(num, k))

Submission status: Accepted

Solution code:
from bisect import bisect
f = open(0)
readline = f.readline
N = int(readline())
*A, = map(int, readline().split())
ans = []
def query(Q):
    for k in map(int, f.read().split()):
        idx = bisect(A, k-1)
        if idx < N and A[idx] == k:
            yield "%d %d\n" % (idx, bisect(A, k))
        else:
            yield "%d %d\n" % (idx, idx)
open(1, 'w').writelines(list(query(int(readline()))))

Submission status: Accepted

Solution code:
import bisect
input(); A = list(map(int, input().split()))
for _ in [0]*int(input()):
    k = int(input())
    print(bisect.bisect_left(A, k), bisect.bisect_right(A, k))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
  k = int(input())
  print(bisect_left(a, k), bisect_right(a, k))