사용자 도구

사이트 도구


ps:problems:boj:1667

지민이의 테러 Season IV

ps
링크acmicpc.net/…
출처BOJ
문제 번호1667
문제명지민이의 테러 Season IV
레벨플래티넘 4
분류

BBST

시간복잡도O(nlogn)
인풋사이즈n<=50000
사용한 언어Python
제출기록43132KB / 1112ms
최고기록1112ms
해결날짜2022/10/13

풀이

  • 장애물 경기과 거의 동일한 문제이다. 동일한 방식으로 최단 거리를 계산한 뒤에, 마지막에 출력하는 답의 형식만 다르다. 풀이는 그쪽을 참고.
  • 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()

토론

댓글을 입력하세요:
T E A J G
 
ps/problems/boj/1667.txt · 마지막으로 수정됨: 2022/10/13 08:19 저자 teferi