====== Dividing the Path ======

===== 풀이 =====
  * 핵심이 되는 DP식은 간단한 편인데, 소들의 선호 범위와, 스플링클러의 최소범위~최대범위를 고려하려면 조금씩 복잡해진다..
  * DP[i]를 [0,i]구간을 모두 스프링클러로 커버하고, 이때 마지막 스프링클러의 범위의 오른쪽 끝이 i가 되게 배치하는 데에 필요한 스프링클러의 최소 갯수라고 하자. 기본적으로는 마지막 스프링클러를 [i-2B, i-2A] 범위에 세우는 경우중에서 최소를 고르면 되기 때문에 $ DP[i] = min_{i-2B \le j \le i-2A}{DP[j]} + 1 $ 형태의 식이 된다. 이 식만 놓고 생각할때, DP값 하나를 갱신하려면 저 범위내 DP값들의 최솟값을 알아야 하고, 나이브하게 최솟값을 구하면 O(2B-2A)이 걸리지만 [[ps:덱#monotone deque]]를 사용하면 amortized O(1)에 처리할수 있다.
  * 다만 여기서 스프링클러의 반지름은 정수이므로, 스프링클러의 커버범위는 짝수가 되어야 하고, 그러면 마지막 스프링클러는 [i-2B, i-2A] 범위에서도 i와의 차가 짝수인 점에만 세울수 있게 된다. 이렇게 되면 deque를 홀수와 짝수로 나눠서 두개를 만들어야 하는 걱정을 할수 있지만, 생각해보면 그냥 스프링클러의 커버 범위가 [0,i]가 되면, i는 무조건 짝수여야 한다는 것을 알수 있다. 따라서 i가 홀수일때는 그냥 dp[i]=INF로 주면 된다.
  * 그리고, i가 어떤 소의 선호범위 안에 들어가있는 경우에는, 그 소의 선호범위를 선호범위를 하나의 스프링클러로 커버하지 못하게 되므로 이경우에도 DP[i]= INF로 주면 된다.
  * 이것들을 반영하고, 범위내의 최솟값을 [[ps:덱#monotone deque]]를 이용해서 관리하면서 DP테이블을 채워나가면 해결할수 있다. DP값 하나를 계산하는 시간이 amortized O(1)이므로 총 시간복잡도는 O(L)이 된다.
  * [[ps:덱#monotone deque]]으로 DP를 푸는 흔한 문제들과는 다르게, 덱이 관리하는 구간의 우측 끝이 현재 갱신한 dp값의 위치와 같지 않기 때문에, 구현할때 좀더 신경을 써야 한다.


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 7041. Dividing the Path".

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

Tags: [DP] [Monotone deque]
"""

import collections
import sys

INF = float('inf')


def main():
    N, L = [int(x) for x in sys.stdin.readline().split()]
    A, B = [int(x) for x in sys.stdin.readline().split()]
    interval_left_count, interval_right_count = [0] * (L + 1), [0] * (L + 1)
    for _ in range(N):
        S, E = [int(x) for x in sys.stdin.readline().split()]
        interval_left_count[S] += 1
        interval_right_count[E] += 1

    min_range, max_range = A * 2, B * 2
    deq = collections.deque([INF])
    dp = [None] * (L + 1)
    dp[0] = 0
    interval_count = interval_left_count[0] - interval_right_count[0]
    for i in range(1, L + 1):
        interval_count -= interval_right_count[i]
        if i % 2 == 1 or interval_count > 0:
            dp[i] = INF
        else:
            dp[i] = deq[0] + 1
        interval_count += interval_left_count[i]
        if (right := i + 1 - min_range) >= 0:
            val_to_add = dp[right]
            while deq and deq[-1] > val_to_add:
                deq.pop()
            deq.append(val_to_add)
        if (left := i - max_range) >= 0:
            if deq[0] == dp[left]:
                deq.popleft()

    print('-1' if dp[-1] == INF else dp[-1])


if __name__ == '__main__':
    main()
</dkpr>

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