지민이의 테러 Season IV

• 장애물 경기과 거의 동일한 문제이다. 동일한 방식으로 최단 거리를 계산한 뒤에, 마지막에 출력하는 답의 형식만 다르다. 풀이는 그쪽을 참고.
• BBST의 용도로 OrderStatisticTree를 사용했는데, 그러기 위해서 음수와 양수가 섞여있는 좌표들을 모두 양수가 되도록 매핑하는 작업이 추가로 필요했다.
• 중요한 부분인데, 문제의 한글 번역과 원문, 실제 데이터가 조금씩 어긋나 있다.. 실제 입력은 S에 가까운 펜스부터 차례로 주어진다.

"""Solution code for "BOJ 1667. 지민이의 테러 Season IV".

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

Tags: [BBST]
"""

import itertools
import sys
from teflib import fenwicktree

INF = float('inf')


def get_nums_between(ost, beg, end):
    k = ost.count_less_than(beg)
    ret = []
    for i in range(k + 1, ost.size() + 1):
        nums = ost.kth(i)
        if nums >= end:
            break
        ret.append(nums)
    return ret


def main():
    N, S = [int(x) for x in sys.stdin.readline().split()]
    A_and_B = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]
    min_x = min(0, S, min(itertools.chain.from_iterable(A_and_B)))
    max_x = max(0, S, max(itertools.chain.from_iterable(A_and_B)))

    ost = fenwicktree.OrderStatisticTree(max_x - min_x + 1)
    ost.add(S - min_x)
    dist_by_pos = {S - min_x: 0}
    for a_i, b_i in A_and_B:
        l, r = a_i - min_x, b_i - min_x
        blocked_positions = get_nums_between(ost, l, r + 1)
        if not blocked_positions:
            continue
        dist_l = dist_r = INF
        for x in blocked_positions:
            ost.add(x, -1)
            dist = dist_by_pos.pop(x)
            dist_l = min(dist_l, dist + x - l)
            dist_r = min(dist_r, dist + r - x)
        ost.add(l)
        ost.add(r)
        dist_by_pos[l] = dist_l
        dist_by_pos[r] = dist_r

    answer = min(abs(x + min_x) + dist for x, dist in dist_by_pos.items())
    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.fenwicktree.FenwickTree