====== 지민이의 테러 Season IV ======

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

===== 코드 =====
<dkpr py>
"""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()

</dkpr>
  * Dependency: [[:ps:teflib:fenwicktree#FenwickTree|teflib.fenwicktree.FenwickTree]]

{{tag>BOJ ps:problems:boj:플래티넘_4}}