• f의 합이 M 이상인 구간 중에서, max(s)값이 최소인 구간을 찾는 문제이다.
• 원래 이 문제를 O(nlogn)으로 푸는 세가지 방법을 열심히 적어놨었는데, 뒤늦게 O(n)으로 푸는 방법을 떠올리게 되었다… 원래 적어두었던 방법들은 지우지 않고 밑에 남겨두었다.
• max(s)은 포함하는 원소가 적을수록 작아지므로, 현재 구간의 f값이 M이상이면, 더 큰 구간에 대해서는 볼 필요가 없다. 따라서 그냥 투 포인터 방법을 사용해서 합이 M이상인 구간들을 트래킹하면서, 구간의 최대값을 비교해주면 된다.
• 구간의 최댓값을 갱신하는 것을 monotone queue를 사용하면, 총 시간복잡도를 O(n)으로 유지하면서 문제를 풀수가 있다. 이 테크닉에 대한 설명은 링크 참고.
  • 원래 예전에는 monotone queue를 사용한다는 생각을 못했고, 그냥 우선순위 큐 (Priority Queue)를 이용해서 처리했다. 그래서 시간복잡도가 O(nlogn)이었고, 지금 플이보다 유의미하게 느렸다.
• 이하는 예전에 올렸던 풀이…
• max(s)은 포함하는 원소가 적을수록 작아지므로, 현재 구간의 f값이 M이상이면, 더 큰 구간에 대해서는 볼 필요가 없다. 따라서 그냥 투 포인터 방법을 사용해서 합이 M이상인 구간들을 트래킹하면서, 구간의 최대값을 비교해주면 된다
• 구간의 최대값을 저장하고 갱신하는 것은 heap을 이용한다. 우측 포인터를 이동시켜서 구간이 넓어지면 원소를 추가하고, 좌측 포인터를 이동시켜서 구간이 좁아지면 원소를 삭제해야 한다. 힙에 원소 삭제를 처리하기 위해서 그냥 heapq 대신에 teflib.ps:teflib:priorityqueue.UpdatableHeap 를 사용했다. 그러면 n번의 삽입,삭제,최대값검색을 처리해야 하므로 총 시간복잡도는 O(nlogn).
• 이것과는 전혀 다른 방식의 그리디한 풀이도 존재한다. s값이 작은 음식부터 정렬하고 하나씩 꺼낸다. 만약 인접한 음식의 s값이 현재 값보다 작거나 같으면, 합쳐서 하나의 그룹으로 묶을수 있고, 그 그룹의 최대 s값을 방금 꺼낸 음식의 s값으로 갱신할수 있다. 이렇게 인접한 음식들을 묶어서 그룹을 만들다가, 그룹의 f값의 합이 M 이상이 되면 종료하면 된다.
• 이 방식은 그룹을 처리하기 위해서 Disjoint Set을 사용한다. 처음에 정렬하는데에 O(nlogn), 그리고 O(n)번의 union/find 연산을 처리하는 데에 O(n*α(n))이 걸린다. 이 방법 역시, 총 시간복잡도는 O(nlogn).
• s값이 특정값 이하인 음식들만으로 그룹을 만들어서 그룹의 f값이 M이상이 되는지 확인한다라는 아이디어까지만 떠올리는데에 성공했으면 그냥 이분탐색을 이용해서 최소의 s값을 찾을수도 있다. 가장 작은 s값부터 시작해서 그룹을 계속 키워 나가며 비교하는 것보다, 이 편이 더 발상과 구현 모두 간단하다. s값이 특정값 이하이면서 f값이 M이상인 그룹이 있는지를 체크하는 것은 O(n)에 가능하므로, 총 시간복잡도는 O(nlogn)이다. (그냥 0~max(S) 까지 파라메트릭 서치를 돌리면. O(nlog(max(S))가 되겠지만, 답이 될수 있는 값은 S_i 중 하나이므로 그냥 S값들에 대해서만 이분탐색을 돌리면 된다)
• 세 방법의 실행시간에 큰 차이는 없었다. 아래 제출한 코드만 놓고 보면 이분탐색 > 투포인터+힙 > 디스조인트셋 순서로 빨랐지만.. 투포인터는 typing을 임포트하는데에 시간이 걸리고, 디스조인트셋은 입력처리에 시간이 걸리게 구현되어 있는 것을 생각하면, 100ms 내외의 차이는 무시해도 된다.

"""Solution code for "BOJ 15459. Haybale Feast".

- Problem link: https://www.acmicpc.net/problem/15459
- Solution link: http://www.teferi.net/ps/problems/boj/15459

Tags: [Two pointer] [Monotone queue]
"""

import collections
import sys

INF = float('inf')


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    F_and_S = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    left, right = iter(F_and_S), iter(F_and_S)
    tot_flavor = 0
    spiciness_deq = collections.deque()
    answer = INF
    while True:
        if tot_flavor < M:
            try:
                f, s = next(right)
            except StopIteration:
                break
            tot_flavor += f
            while spiciness_deq and spiciness_deq[-1] < s:
                spiciness_deq.pop()
            spiciness_deq.append(s)
        else:
            answer = min(answer, spiciness_deq[0])
            f, s = next(left)
            tot_flavor -= f
            if s == spiciness_deq[0]:
                spiciness_deq.popleft()

    print(answer)


if __name__ == '__main__':
    main()

"""Solution code for "BOJ 15459. Haybale Feast".

- Problem link: https://www.acmicpc.net/problem/15459
- Solution link: http://www.teferi.net/ps/problems/boj/15459

Tags: [Two pointer] [Priority queue]
"""

import sys
from teflib import priorityqueue

INF = float('inf')


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    F_and_S = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    spiciness_heap = priorityqueue.UpdatableHeap()
    left, right = iter(F_and_S), iter(F_and_S)
    tot_flavor = 0
    answer = INF
    while True:
        if tot_flavor < M:
            try:
                f, s = next(right)
            except StopIteration:
                break
            tot_flavor += f
            spiciness_heap.push(-s)
        else:
            answer = min(answer, -spiciness_heap.top())
            f, s = next(left)
            tot_flavor -= f
            spiciness_heap.delete(-s)

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.ps:teflib:priorityqueue.UpdatableHeap

"""Solution code for "BOJ 15459. Haybale Feast".

- Problem link: https://www.acmicpc.net/problem/15459
- Solution link: http://www.teferi.net/ps/problems/boj/15459

Tags: [Disjoint set]
"""

import operator
import sys
from teflib import disjointset


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    F, S = zip(
        *([int(x) for x in sys.stdin.readline().split()] for _ in range(N)))

    dsu = disjointset.DisjointSet(N)
    flavor_by_set = list(F)
    for i, S_i in sorted(enumerate(S), key=operator.itemgetter(1)):
        flavor_cur = F[i]
        if i > 0 and S[i - 1] <= S_i:
            flavor_left = flavor_by_set[dsu.find(i - 1)]
            merged_set = dsu.union(i - 1, i)
            flavor_cur = flavor_by_set[merged_set] = flavor_cur + flavor_left
        if i + 1 < N and S[i + 1] <= S_i:
            flavor_right = flavor_by_set[dsu.find(i + 1)]
            merged_set = dsu.union(i + 1, i)
            flavor_cur = flavor_by_set[merged_set] = flavor_cur + flavor_right
        if flavor_cur >= M:
            print(S_i)
            break


if __name__ == '__main__':
    main()

• Dependency: teflib.ps:disjointset.DisjointSet

"""Solution code for "BOJ 15459. Haybale Feast".

- Problem link: https://www.acmicpc.net/problem/15459
- Solution link: http://www.teferi.net/ps/problems/boj/15459

Tags: [Binary search]
"""

import bisect
import sys

def main():

    def is_valid(s):
        f_sum = 0
        for f_i, s_i in F_and_S:
            if s_i > s:
                f_sum = 0
            else:
                f_sum += f_i
                if f_sum >= M:
                    return True
        return False

    N, M = [int(x) for x in sys.stdin.readline().split()]
    F_and_S = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    s_sorted = sorted(set(s for f, s in F_and_S))
    min_s_ind = bisect.bisect_left(s_sorted, True, key=is_valid)
    print(s_sorted[min_s_ind])


if __name__ == '__main__':
    main()