Problem p02788 (python)

Fixed submission:
import bisect

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]

XH.sort()
X, H = zip(*XH)

K = [-(-h // A) for h in H]
L = [0] * (N + 2)

ans = 0
for i in range(N):
    L[i + 1] += L[i]
    s = max(K[i] - L[i + 1], 0)
    ans += s
    L[i + 1] += s
    L[bisect.bisect_right(X, X[i] + 2 * D) + 1] -= s

print(ans)

Buggy submission (verdict: Runtime Error):
import bisect

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]


class BIT:
    def __init__(self, n=None):
        # 1-index
        if n is None:
            n = (1 << 20) - 1
        self.n = n
        self.dat_a = [0] * (2 * self.n - 1)
        self.dat_b = [0] * (2 * self.n - 1)

    def add(self, a, b, x, k=0, l=0, r=None):
        # Add x to [a, b)
        if r is None:
            r = self.n

        if a <= l and r <= b:
            self.dat_a[k] += x
        elif l < b and a < r:
            self.dat_b[k] += (min(b, r) - max(a, l)) * x
            self.add(a, b, x, k * 2 + 1, l, (l + r) // 2)
            self.add(a, b, x, k * 2 + 2, (l + r) // 2, r)
            
    def query(self, a, b, k=0, l=0, r=None):
        # Retrun sum of [a, b)
        if r is None:
            r = self.n
        
        if b <= l or r <= a:
            return 0
        
        if a <= l and r <= b:
            return self.dat_a[k] * (r - l) + self.dat_b[k]
        
        res = (min(b, r) - max(a, l)) * self.dat_a[k]
        res += self.query(a, b, k * 2 + 1, l, (l + r) // 2)
        res += self.query(a, b, k * 2 + 2, (l + r) // 2, r)
        
        return res

X, H = zip(*sorted(XH))
bit = BIT(N + 10)

# 初期化
for i, h in enumerate(H):
    bit.add(i + 1, i + 2, h)
    
# 処理
res = 0
for i in range(N):
    cur = bit.query(i + 1, i + 2)
    if cur <= 0:
        continue

    need = -(-cur // A)
    idx = bisect.bisect_right(X, X[i] + 2 * D)
    bit.add(i + 1, idx + 1, -need * A)
    res += need
    
print(res)

Buggy submission (verdict: Runtime Error):
N, D, A = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]

class BIT:
    def __init__(self, n=None):
        # 1-index
        if n is None:
            n = (1 << 20) - 1
        self.n = n
        self.dat_a = [0] * (2 * self.n - 1)
        self.dat_b = [0] * (2 * self.n - 1)

    def add(self, a, b, x, k=0, l=0, r=None):
        # Add x to [a, b)
        if r is None:
            r = self.n

        if a <= l and r <= b:
            self.dat_a[k] += x
        elif l < b and a < r:
            self.dat_b[k] += (min(b, r) - max(a, l)) * x
            self.add(a, b, x, k * 2 + 1, l, (l + r) // 2)
            self.add(a, b, x, k * 2 + 2, (l + r) // 2, r)
            
    def query(self, a, b, k=0, l=0, r=None):
        # Retrun sum of [a, b)
        if r is None:
            r = self.n
        
        if b <= l or r <= a:
            return 0
        
        if a <= l and r <= b:
            return self.dat_a[k] * (r - l) + self.dat_b[k]
        
        res = (min(b, r) - max(a, l)) * self.dat_a[k]
        res += self.query(a, b, k * 2 + 1, l, (l + r) // 2)
        res += self.query(a, b, k * 2 + 2, (l + r) // 2, r)
        
        return res


ans = 0
bit = BIT()
X.sort(key=lambda x:x[0])
for x, h in X:
    res = h - bit.query(x, x + 1)
    if res <= 0:
        continue
        
    cnt = -(-res // A)
    bit.add(x, x + 2 * D + 1, cnt * A)
    ans += cnt
    
print(ans)

Buggy submission (verdict: Runtime Error):
N, D, A = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]

class BIT:
    def __init__(self, n=None):
        # 1-index
        if n is None:
            n = (1 << 18) - 1
        self.n = n
        self.dat_a = [0] * (2 * self.n - 1)
        self.dat_b = [0] * (2 * self.n - 1)

    def add(self, a, b, x, k=0, l=0, r=None):
        # Add x to [a, b)
        if r is None:
            r = self.n

        if a <= l and r <= b:
            self.dat_a[k] += x
        elif l < b and a < r:
            self.dat_b[k] += (min(b, r) - max(a, l)) * x
            self.add(a, b, x, k * 2 + 1, l, (l + r) // 2)
            self.add(a, b, x, k * 2 + 2, (l + r) // 2, r)
            
    def query(self, a, b, k=0, l=0, r=None):
        # Retrun sum of [a, b)
        if r is None:
            r = self.n
        
        if b <= l or r <= a:
            return 0
        
        if a <= l and r <= b:
            return self.dat_a[k] * (r - l) + self.dat_b[k]
        
        res = (min(b, r) - max(a, l)) * self.dat_a[k]
        res += self.query(a, b, k * 2 + 1, l, (l + r) // 2)
        res += self.query(a, b, k * 2 + 2, (l + r) // 2, r)
        
        return res


ans = 0
bit = BIT()
X.sort(key=lambda x:x[0] - x[1])
for x, h in X:
    res = h - bit.query(x, x + 1)
    if res <= 0:
        continue
        
    cnt = -(-res // A)
    bit.add(x, x + 2 * D + 1, cnt * A)
    ans += cnt
    
print(ans)