[boj] 백준 12099 점심메뉴 python 풀이

문제

https://www.acmicpc.net/problem/12099

12099번: 점심메뉴

 

 

문제 풀이

매운맛 범위를 이분탐색해서 한번 범위를 좁혀주고, 단맛의 범위를 이분탐색으로 찾기

 

코드

import sys
input = sys.stdin.readline
import bisect

N, Q = map(int,(input().split()))
menu = [list(map(int,input().split())) for _ in range(N)]
menu.sort()
spicy = list(zip(*menu))[0]
sweet = list(zip(*menu))[1]
Q_list = [list(map(int,input().split())) for _ in range(Q)]

for q in Q_list:
    l = bisect.bisect_left(spicy, q[0])
    r = bisect.bisect_right(spicy, q[1])

    tmp= sorted(sweet[l:r])
    l = bisect.bisect_left(tmp, q[2])
    r = bisect.bisect_right(tmp, q[3])
    print(r-l)