백준 12099번: 점심메뉴 [Python]

작성일 | In
골드 IV 골드 IV

문제

점심메뉴

풀이

$i$번째 음식의 매운맛 수치를 $a_i$, 단맛 수치를 $b_i$라 합시다.

$v \le u + 10000$이고 매운맛 수치는 각각 유일하므로 $u \le a_i \le v$인 $i$의 개수는 $10000$이 넘지 않습니다. 따라서 $i$의 최소, 최대는 이분 탐색으로 찾은 뒤 $[x, y]$는 직접 검사해주면 됩니다.

시간 복잡도는 $\mathcal{O}(\log N + 10000N)$입니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from dataclasses import dataclass
from bisect import bisect_left, bisect_right
from typing import Callable


@dataclass(order=True)
class Food:
    spiciness: int
    sweetness: int


def main():
    N, Q = map(int, input().split())

    foods: list[Food] = []
    for _ in range(N):
        foods.append(Food(*map(int, input().split())))
    foods.sort()

    for _ in range(Q):
        u, v, x, y = map(int, input().split())

        key: Callable[[Food], int] = lambda x: x.spiciness
        lo = bisect_left(foods, u, key=key)
        hi = bisect_right(foods, v, key=key)

        ans = 0
        for i in range(lo, hi):
            if x <= foods[i].sweetness <= y:
                ans += 1

        print(ans)


main()

백준 12099번: 점심메뉴 [Python]