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)이 걸리지만 monotone deque를 사용하면 amortized O(1)에 처리할수 있다.
• 다만 여기서 스프링클러의 반지름은 정수이므로, 스프링클러의 커버범위는 짝수가 되어야 하고, 그러면 마지막 스프링클러는 [i-2B, i-2A] 범위에서도 i와의 차가 짝수인 점에만 세울수 있게 된다. 이렇게 되면 deque를 홀수와 짝수로 나눠서 두개를 만들어야 하는 걱정을 할수 있지만, 생각해보면 그냥 스프링클러의 커버 범위가 [0,i]가 되면, i는 무조건 짝수여야 한다는 것을 알수 있다. 따라서 i가 홀수일때는 그냥 dp[i]=INF로 주면 된다.
• 그리고, i가 어떤 소의 선호범위 안에 들어가있는 경우에는, 그 소의 선호범위를 선호범위를 하나의 스프링클러로 커버하지 못하게 되므로 이경우에도 DP[i]= INF로 주면 된다.
• 이것들을 반영하고, 범위내의 최솟값을 monotone deque를 이용해서 관리하면서 DP테이블을 채워나가면 해결할수 있다. DP값 하나를 계산하는 시간이 amortized O(1)이므로 총 시간복잡도는 O(L)이 된다.
• monotone deque으로 DP를 푸는 흔한 문제들과는 다르게, 덱이 관리하는 구간의 우측 끝이 현재 갱신한 dp값의 위치와 같지 않기 때문에, 구현할때 좀더 신경을 써야 한다.

"""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()