提出 #44605778

---

ソースコード 拡げる

import bisect
n, l, r = map(int, input().split())
a = list(map(int, input().split()))
class SegmentTree(): # 0-indexed で書く．
    def __init__(self, n):
        self.siz = 1
        while self.siz < n:
            self.siz *= 2
        self.dat = [0 for _ in range(2 * self.siz)]
    def update(self, p, x):
        p += self.siz
        self.dat[p] = x
        while p >= 2:
            p //= 2
            self.dat[p] = min(self.dat[p * 2], self.dat[(p * 2) + 1]) # 問題依存
    def rpd(self, l, r, a, b, nw):
        # st.rpd(l, r, 1, st.siz + 1, 1)で求まる．
        if r <= a or b <= l:
            return 10 ** 10 # 問題依存
        if l <= a and b <= r:
            return self.dat[nw]
        m = (a + b) // 2
        al = self.rpd(l, r, a, m, nw * 2)
        ar = self.rpd(l, r, m, b, nw * 2 + 1)
        return min(al, ar) # 問題依存
st = SegmentTree(n)
dp = [10 ** 9 for _ in range(n)]
dp[0] = 0
for i in range(n):
    st.update(i, dp[i])
for i in range(1, n):
    bl = a[i] - r
    br = a[i] - l
    il = bisect.bisect_left(a, bl)
    ir = bisect.bisect_right(a, br)
    rqr = st.rpd(il, ir, 0, st.siz, 1)
    dp[i] = rqr + 1
    st.update(i, dp[i])
print(dp[n - 1])

提出情報

ジャッジ結果